[Algorithm] Quick Sort (퀵정렬) C++

1. 퀵정렬 정의

임의로 pivot 잡은 후 pivot보다 작은 그룹을 왼쪽. 큰 그룹을 오른쪽으로 분할하여 해결한다. (분할 정복 방법)

• 분할 정복 방법 (divide-and-conquer) 
  • 큰 문제를 작은 문제 단위로 쪼개면서 해결한다.
  • 문제를 2개의 문제로 분리하는데, 원소개수가 1개가 될 때까지 분리한다. 그 다음 작은 문제에서부터 결과를 모아 원래 문제를 해결한다.
  • 멀리 있는 값들끼리 교환이 일어나므로 불안정한 정렬이다.
• 퀵정렬은 분할, 정복, 결합 단계로 이뤄진다.
  • 분할(Divide): 피벗을 중심으로 피벗보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 분할한다.
  • 정복(Conquer): 부분 배열을 정렬한다.
  • 결합(Combine): 정렬된 부분 배열들을 하나의 배열로 합친다.

 

2. 퀵정렬 특징

- 장점

빠르다 -> O(nlogn)

 

- 단점

최악의 경우 느리다. -> O(n^2)

 

3. 시간 복잡도

- Best Case

피벗을 잘 잡아, 부분배열의 개수가 n/2로 나눠질 경우 : O(nlogn)

Recursion Tree의 깊이 : 최대 logn 이기 때문

 

- Worst Case

부분배열 개수가 불균형하게 분할 되는 경우(n-1,0개) : O(n^2)

Recursion Tree의 깊이 : 최대 n 이기 때문

 

4. 구현 방법 (C++)

#include <algorithm>   //swap

void quickSort(int A[], int low, int high) {
    if(low >= high) return; // base condition

    // divide process
    int i = low, j = low;
    int&pivot = A[high];
    for (; j < high; ++j) {
        if ( A[j] < pivot)
            swap(A[i++], A[j]);
    }
    swap(A[i], pivot);

    // conquer process
    quickSort(A, low, i-1);
    quickSort(A, i+1, high);
}