Algorithm : Sorting (4)

Nekoder

---

예제 Quicksort

---

 

퀵소트를 구현하되, 피벗 선택 방식은 median-of-three 컷오프 = 3(배열 크기가 3 이하면 삽입 정렬 사용)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//insertionsort (<= cutoff)
template <typename Comparable>
void insertionSort(vector<Comparable>& a, int left, int right) {
    for (int p = left + 1; p <= right; ++p) {
        Comparable tmp = a[p];
        int j = p;
        while (j > left && tmp < a[j-1]) {
            a[j] = a[j-1];
            --j;
        }
        a[j] = std::move(tmp);
    }
}

//median-of-three
template<typename Comparable>
const Comparable& median3(vector<Comparable>& a, int left, int right){
    int centor = (left + right) / 2;

    if (a[centor] < a[left]) {
        swap(a[left], a[centor]);
    }
    if (a[right] < a[left]) {
        swap(a[left], a[right]);
    }
    if (a[right] < a[centor]) {
        swap(a[centor], a[right]);
    }
    swap(a[centor], a[right - 1]);
    return a[right - 1];
}

//quicksort
template<typename Comparable>
void quickSort(vector<Comparable>& a, int left, int right){
    const int CUTOFF = 3;

    if(left + CUTOFF <= right) {
        Comparable pivot = median3(a, left, right);

        int i = left, j = right - 1;
        while(true){
            while(a[++i] < pivot) {}
            while(pivot < a[--j]) {}
            if (i < j){
                swap(a[i], a[j]);
            }
            else break;
        }
        swap(a[i], a[right-1]);

        quickSort(a, left, i-1);
        quickSort(a, i+1, right);
    }
    else {
        insertionSort(a, left, right);
    }
}

template<typename Comparable>
void quickSort(vector<Comparable>& a){
    quickSort(a, 0, a.size() - 1);
}

int main() {
    vector<int> data = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    quickSort(data);

    for(int x : data){
        cout << x << " ";
    }
    cout << endl;
}

 

출력

1 1 2 3 3 4 5 5 5 6 9

 

1. InsertionSort

template <typename Comparable>
void insertionSort(vector<Comparable>& a, int left, int right)

먼저 배열 크기가 작을 때 삽입 정렬을 사용하게끔 했습니다.

for (int p = left + 1; p <= right; ++p) {
    Comparable tmp = a[p];
    int j = p;
    while (j > left && tmp < a[j - 1]) {
        a[j] = a[j - 1];
        --j;
    }
    a[j] = std::move(tmp);
}

 tmp를 삽입할 위치를 찾으면서 계속 앞으로 밀어내고, std::move를 사용해서 tmp의 값을 복사 없이 이동시킵니다.

 

2. median3

template<typename Comparable>
const Comparable& median3(vector<Comparable>& a, int left, int right)

median-of-three pivot 선택 : 퀵소트 성능 개선용. 

left, centor, right 중 중간값을 피벗으로 선택하고, 해당 값을 a[right-1] 위치로 이동시킵니다.

int center = (left + right) / 2;

if (a[center] < a[left]) swap(a[left], a[center]);
if (a[right] < a[left]) swap(a[left], a[right]);
if (a[right] < a[center]) swap(a[center], a[right]);

swap(a[center], a[right - 1]);  // 피벗을 우측 끝-1로 이동

이 과정을 통해서 작은 값은 앞, 큰 값은 뒤로 배치합니다.

실제 partition 과정에서 a[right-1]에 있는 pivot을 기준으로 정렬하게 됩니다.

 

3. quickSort

template<typename Comparable>
void quickSort(vector<Comparable>& a, int left, int right)

재귀적으로 퀵소트를 수행하는 메인 알고리즘입니다. CUTOFF 이하이면 insertionSort로 전환되고, 그 외에는 median3으로 피벗 선택한 후에 partition을 수행합니다.

if (left + CUTOFF <= right) {
    Comparable pivot = median3(a, left, right);

    int i = left, j = right - 1;
    while (true) {
        while (a[++i] < pivot) {}
        while (pivot < a[--j]) {}
        if (i < j) swap(a[i], a[j]);
        else break;
    }
    swap(a[i], a[right - 1]); // 피벗 제자리로 복원

    quickSort(a, left, i - 1);   // 왼쪽 구간
    quickSort(a, i + 1, right);  // 오른쪽 구간
}
else {
    insertionSort(a, left, right);  // 작은 배열이면 삽입 정렬
}

while(true) 루프는 partition

재귀적으로 왼쪽/오른쪽 부분 배열을 다시 퀵소트하며 진행됩니다.

 

4. 외부용 퀵소트 오버로드

template<typename Comparable>
void quickSort(vector<Comparable>& a) {
    quickSort(a, 0, a.size() - 1);
}

외부에서 quickSort(data); 처럼 편하게 호출하도록 제공하는 wrapper함수

 

5. main 함수

int main() {
    vector<int> data = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    quickSort(data);
    for (int x : data) {
        cout << x << " ";
    }
    cout << endl;
}

정렬할 데이터를 준비하고, quickSort() 호출 후 정렬된 결과를 출력합니다.

 

위 문제와 같은 구조이지만, 세 가지 경우에 대해서 퀵소트의 성능 차이를 비교하는 문제.

1. 정렬된 배열

2. 역정렬된 배열

3. 무작위 배열

각 케이스마다 비교 횟수를 측정해서 비교해야합니다.

 

앞에서 다룬 7.19 문제에 주어진 입력을 이 문제에서는 c(랜덤 인풋)으로 잡겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// insertionsort (<= cutoff)
template <typename Comparable>
void insertionSort(vector<Comparable>& a, int left, int right, int& compCount) {
    for (int p = left + 1; p <= right; ++p) {
        Comparable tmp = a[p];
        int j = p;
        while (j > left && ++compCount && tmp < a[j - 1]) {
            cout << "Compare (insertSort): " << tmp << " < " << a[j - 1] << endl;
            a[j] = a[j - 1];
            --j;
        }
        a[j] = std::move(tmp);
    }
}

// median-of-three
template<typename Comparable>
const Comparable& median3(vector<Comparable>& a, int left, int right, int& compCount){
    int center = (left + right) / 2;

    if (++compCount && a[center] < a[left]) {
        swap(a[left], a[center]);
    }
    if (++compCount && a[right] < a[left]) {
        swap(a[left], a[right]);
    }
    if (++compCount && a[right] < a[center]) {
        swap(a[center], a[right]);
    }

    swap(a[center], a[right - 1]);
    return a[right - 1];
}

// quicksort
template<typename Comparable>
void quickSort(vector<Comparable>& a, int left, int right, int& compCount){
    const int CUTOFF = 3;

    if(left + CUTOFF <= right) {
        Comparable pivot = median3(a, left, right, compCount);

        int i = left, j = right - 1;
        while(true){
            while (++i && ++compCount && a[i] < pivot) {
                cout<< "Compare: " << a[i] << " < " << pivot << endl;
            }
            while (--j && ++compCount && pivot < a[j]) {
                cout<< "Compare: " << pivot << " < " << a[j] << endl;
            }
            if (i < j){
                swap(a[i], a[j]);
            } else {
                break;
            }
        }
        swap(a[i], a[right-1]);

        quickSort(a, left, i-1, compCount);
        quickSort(a, i+1, right, compCount);
    }
    else {
        insertionSort(a, left, right, compCount);
    }
}

template<typename Comparable>
void quickSort(vector<Comparable>& a, int& compCount){
    quickSort(a, 0, a.size() - 1, compCount);
}

int main() {
    int compCount;

    // Sorted input
    cout << "\n[Sorted input]" << endl;
    vector<int> data_a = {1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9};
    compCount = 0;
    quickSort(data_a, compCount);
    for(int x : data_a) {
        cout << x << " ";
    }
    cout << "\nTotal comparisons: " << compCount << "\n\n";

    // Reverse input
    cout << "[Reverse input]" << endl;
    vector<int> data_b = {9, 6, 5, 5, 5, 4, 3, 3, 2, 1, 1};
    compCount = 0;
    quickSort(data_b, compCount);
    for(int y : data_b) {
        cout << y << " ";
    }
    cout << "\nTotal comparisons: " << compCount << "\n\n";

    // Random input
    cout << "[Random input]" << endl;
    vector<int> data_c = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    compCount = 0;
    quickSort(data_c, compCount);
    for(int z : data_c) {
        cout << z << " ";
    }
    cout << "\nTotal comparisons: " << compCount << "\n";
}

출력

 

[Sorted input]
Compare: 1 < 4
Compare: 2 < 4
Compare: 3 < 4
Compare: 3 < 4
Compare: 4 < 5
Compare: 4 < 5
Compare: 4 < 5
Compare: 4 < 6
Compare: 1 < 2
Compare: 2 < 3
Compare: 5 < 6
Compare (insertSort): 5 < 6
1 1 2 3 3 4 5 5 5 6 9 
Total comparisons: 30

[Reverse input]
Compare: 1 < 3
Compare: 1 < 2
Compare (insertSort): 2 < 3
Compare: 5 < 6
Compare: 5 < 6
1 1 2 3 3 4 5 5 5 6 9 
Total comparisons: 30

[Random input]
Compare: 1 < 5
Compare: 4 < 5
Compare: 1 < 5
Compare: 3 < 5
Compare: 2 < 5
Compare: 5 < 6
Compare: 1 < 2
Compare: 2 < 5
Compare: 2 < 3
Compare: 2 < 4
Compare: 3 < 4
1 1 2 3 3 4 5 5 5 6 9 
Total comparisons: 32

사용 입력 데이터

 

Case	Data
sorted	{1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9}
reverse	{9, 6, 5, 5, 5, 4, 3, 3, 2, 1, 1}
random	{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}

pivot : median-of-three (left, center, right 중 중간값)

cutoff : 크기 3 이하인 구간은 insertionSort

 

1. Sorted

pivot 선택이 항상 배열의 중간 근처라고 하지만, 실제로 정렬된 데이터에서는 partition이 비효율적으로 일어납니다.(재귀 분할이 쏠린다.) 그러면 비교 횟수가 증가하고, Insertion Sort 효과도 적습니다.

따라서 Sorted + median-of-three = 비효율적.

 

2. Reverse Sorted

median-of-three에서도 pivot은 중간값이지만, 입력이 역순이면 실제 분할이 균형 있게 일어날 수도 있습니다. (특히 중복이 많을 경우) 그리고 작은 구간은 Insertion Sort로 전환되며 비교 횟수가 줄어듭니다.

생각보다 효율적일 수 있습니다.

 

3. Random

일반적으로 퀵소트가 가장 잘 작동하는 상황입니다. pivot 분할이 비교적으로 균등하고, 비교 횟수도 중간 수준입니다. Quicksort가 의도한 대로 작동하는 정상 케이스