퀵 정렬(Quick Sort)

세상의 모든 알고리즘 - 퀵정렬

퀵정렬(Quick Sort)은 대표적인 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 방법을 사용합니다. 이 알고리즘은 평균적으로 가장 빠른 속도를 보이며, 대부분의 정렬 라이브러리에서 사용됩니다.


퀵정렬은 다음과 같은 과정으로 이루어집니다.



피벗(Pivot) 선택: 정렬할 배열에서 하나의 원소를 선택하여 피벗으로 지정합니다. 피벗은 배열을 나누는 기준이 됩니다.

분할: 피벗을 기준으로 배열을 두 개의 부분 배열로 분할합니다. 피벗보다 작은 원소는 왼쪽 부분 배열에, 큰 원소는 오른쪽 부분 배열에 위치시킵니다.

정복: 분할된 부분 배열에 대해 재귀적으로 퀵정렬을 수행합니다. 이때, 각 부분 배열에서 피벗을 다시 선택하고, 분할 및 정복 과정을 반복합니다.

합병: 분할된 부분 배열들이 정렬된 상태로 합병됩니다.


위 과정을 반복하여 전체 배열이 정렬됩니다. 이때, 피벗을 선택하는 방법에 따라 퀵정렬의 성능이 달라집니다. 일반적으로는 배열의 첫 번째 원소나 중간 원소를 피벗으로 선택합니다.


퀵정렬은 평균적으로 O(nlogn)의 시간 복잡도를 가지며, 최악의 경우 O(n^2)의 시간 복잡도를 가집니다. 이는 피벗이 최솟값이나 최댓값으로 선택되는 경우에 발생합니다. 따라서, 피벗을 선택하는 방법을 최적화하여 최악의 경우에도 O(nlogn)의 성능을 보이도록 구현할 수 있습니다.

---

void quicksort(int *data, int start, int end)
{
    if(start>=end) return; 
    int pivot = start;
    int i = start +1;
    int j = end;
    while( i <= j)
    {
        while (data[i] <=data[pivot])
        {
            i++;
        }
        while (data[j] >= data[pivot] && j > start)
        {
            j--;
        }
        if(i > j)
        {
            int tmp = data[j];
            data[j] = data[pivot];
            data[pivot] = tmp;
        }
        else
        {
            int tmp = data[j];
            data[j]= data[i];
            data[i] = tmp;
        }
        quicksort(data, start, j-1);
        quicksort(data, j+1, end);
    }
}