퀵 정렬

개념

분할정복의 한 방법으로서, 평균적으로 매우 빠른 알고리즘에 속합니다. 우리가 라이브러리에서 사용하는 대부분의 정렬 함수는 퀵 정렬을 변형한 것입니다.

분할정복 답게 문제를 분리하여 각각 해결하고 합쳐서 해결하는 방식입니다. 

 

1.  배열안에 있는 요소를 선택합니다. 이렇게 고른 원소를 피봇이라고 합니다. 
2. 피봇을 기준으로 피봇보다 작은 원소들은 왼쪽으로 큰 원소들은 오른쪽으로 옮깁니다.
3. 피봇을 제외한 왼쪽 배열과 오른쪽 배열을 각각 순환 호출을 통하여 피봇을 설정하고 왼쪽 오른쪽으로 나눕니다.
4. 배열이 더이상 분할이 불가능할 때까지 반복합니다. 

 

즉 피봇을 기준으로 분할하고 분할된 배열들을 합하여 정렬된 배열이 되게 하는 알고리즘입니다.

 

분할 정복기준으로 단계를 나누면 아래와 같습니다.

• Divide: 입력 배열을 피봇을 기준으로 비균등하게 2개의 부분 배열(피봇을 중심으로 왼쪽: 피봇보다 작은 요소들, 오른쪽: 피봇보다 큰 요소들)로 분할합니다.
• Conquer: 부분배열을 정렬합니다. 부분배열의 크기가 충분치않으면 순환호출을 통해 다시 분할정복 기법을 적용합니다.
• Combine: 정렬된 배열들을 합칩니다.

 

 

void swap(vector<int> &arr, int left, int right) {
    int tmp = arr[left];
    arr[left] = arr[right];
    arr[right] = tmp;
}

int partition(vector<int> &arr, int left, int right) {// divide
    // conquer
    int pivot = arr[left];
    int low = left;
    int high = right + 1;

    do {
        do {
            low++;//left +1에서 시작해서 pivot보다 큰게 생기면 pivot보다 작은 high와 swap한다.
        } while (low <= right && arr[low] < pivot);

        do {
            high--;// right에서 시작해서 pivot보다 작은게 생기면 low와 교환한다.
        } while (high >= left && arr[high] > pivot);

        if (low < high) {
            swap(arr, low, high);
        }
    } while (low < high);//둘이가 만나면 끝.
    // pivot은 여전히 left위치이므로 high와 교환
    swap(arr, left, high);// low와 교환할시에는 더 큰것과 교환될지도 모른다. 
    return high;
}


void quick_sort(vector<int> &arr, int left, int right) {//부분배열의 범위를 위해 left, right을 인자로 받는다.
    // divide

    if (left < right) {//

        int a = partition(arr, left, right);

        quick_sort(arr, left, a - 1);
        quick_sort(arr, a, right);
    }

}

 

장점

• 속도가 빠르다.
• 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
• 추가 메모리 공간을 필요로 하지 않는다.
• 퀵 정렬은 O(n)만큼의 메모리를 필요로 한다.

단점

• 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
• 퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택한다.
  
  • EX) 리스트 내의 몇 개의 데이터 중에서 크기순으로 중간 값(medium)을 피벗으로 선택한다.

퀵 정렬의 시간복잡도

- 최선의 경우

최선의 경우는 pivot의 위치가 중앙으로 오는 경우입니다.  pivot이 중앙으로 오게 됨으로써 divide가 이분할되기때문입니다.

따라서 순환호출의 깊이는 K = log2n이 되게 되고 

각 순환호출에서는 n번가량의 비교연산이 일어납니다.( swap은 상수로 무시합니다.)

 

따라서 최종적인 시간복잡도는 O( n * log2n)입니다.

 

 

- 최악의 경우

 

최악의 경우는 pivot의 위치가 각 부분배열의 제일 왼쪽이나 오른쪽에 생기는 경우입니다. 

이 경우 순환 호출의 깊이는 시퀀스가 되어 n이 됩니다. 

또 각 순환호출의 비교연산은 n이므로 최종적인 시간복잡도는 O(n^2)가 됩니다.