Quick Sort

퀵 정렬은 분할 정복(Divide and Conquer) 알고리즘의 일종으로, 평균적으로 $O(n \log n)$의 시간 복잡도를 가지는 매우 효율적인 정렬 알고리즘이다.

퀵 정렬은 피벗(Pivot)이라는 기준점을 선택한 후, 피벗보다 작은 요소들은 왼쪽에, 큰 요소들은 오른쪽에 배치하는 과정을 재귀적으로 반복하여 정렬을 수행합니다.

퀵 정렬의 단계

---

1. 피벗 선택 : 배열에서 하나의 요소를 피벗으로 선택합니다. 일반적으로 배열의 마지막 요소를 피벗으로 선택합니다.

2. 분할 : 피벗을 기준으로 배열을 분할합니다. 피벗보다 작은 요소들은 왼쪽에, 큰 요소들은 오른쪽에 배치되도록 배열을 재정렬합니다.

3. 재귀적 정렬 : 분할된 두 개의 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다. 이 과정을 배열의 크기가 1이 될 때까지 반복합니다.

이미지 출처

퀵 정렬 예시 코드

---

#include <stdio.h>

void quicksort(int ary[], int left, int right) {
    if (left < right) {
        int pivotIndex = partition(ary, left, right);
        quicksort(ary, left, pivotIndex - 1);
        quicksort(ary, pivotIndex + 1, right);
    }
}

int partition(int ary[], int left, int right) {
    int pivot = ary[right];
    int i = left - 1;

    for (int j = left; j < right; j++) {
        if (ary[j] <= pivot) {
            i++;
            int temp = ary[i];
            ary[i] = ary[j];
            ary[j] = temp;
        }
    }

    int temp = ary[i + 1];
    ary[i + 1] = ary[right];
    ary[right] = temp;
    return i + 1;
}

int main(void) {
    int ary[] = { 3, 7, 8, 5, 2, 1, 9, 5, 4 };
    int n = sizeof(ary) / sizeof(ary[0]);

    quicksort(ary, 0, n - 1);

    for (int i = 0; i < n; i++) {
        printf("%d ", ary[i]);
    }
    return 0;
}

장점

---

효율성 : 평균적으로 $O(n \log n)$의 시간 복잡도를 가지며, 실제로도 빠르게 동작합니다.

제자리 정렬 : 추가적인 메모리 사용 없이 정렬을 수행합니다.

단점

---

최악의 경우 : 피벗이 항상 최소 또는 최대 값으로 선택될 경우, 시간 복잡도가 $O(n^2)$로 악화될 수 있습니다.
하지만, 랜덤 피벗 선택 또는 삼중 피벗 방식을 사용하면 최악의 경우를 회피할 수 있습니다.

---

퀵 정렬은 많은 경우에 있어 효율적인 선택이며, C 언어의 qsort 함수는 퀵 정렬을 내부적으로 사용하여 매우 빠른 정렬을 제공합니다.