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

퀵 정렬(Quick Sort)

• 퀵 정렬은 분할 정복(Divide and Conquer) 알고리즘 을 이용하여 구현됨.
• 병합 정렬과 퀵 정렬의 비교
  • 병합 정렬(Merge Sort)
    • 대용량의 데이터 정렬
  • 퀵 정렬(Quick Sort)
    • 평균 실행 시간을 줄이는 것
    • 기본 아이디어는 병합 정렬과 같음.
      • 원본 입력 배열을 작은 크기의 부분 배열로 나눔.
      • 각 부분 배열을 정렬함.
      • 그 결과를 합쳐서 전체 정렬 배열을 생성함.
    • 핵심
      • 병합(Combine)이 아니라 분할(Split)
• 입력 배열이 주어지고, 입력 배열 중 피벗(Pivot) 원소 P를 선택했을 경우, 퀵 정렬을 위한 분할 연산 은 다음의 2단계로 이루어짐.
  • ① 입력 배열을 2개의 부분 배열 R과 L로 나눔.
    • L
      • 입력 배열에서 P 보다 작거나 같은 원소를 포함하는 부분 배열
      • element(L) <= P
    • R
      • 입력 배열에서 P보다 큰 원소를 포함하는 부분 배열
      • element(R) > P
  • ② 입력 배열을 L, P, R 순서로 재구성함.

• 이러한 방식으로 분할 연산을 수행하면, 피벗 P는 배열이 최종적으로 정렬되었을 때 P가 실제로 있어야 하는 위치로 이동하게 됨.
  • 예) 위의 그림의 경우, 피벗 원소 5가 분할 연산 후 배열의 5번째 위치로 이동함.
    • 배열 전체를 오름차순으로 정렬했을 경우, 원소 5가 있어야 하는 위치와 같음.
• 이러한 특징은 퀵 정렬의 핵심 아이디어이며, 전체 퀵 정렬 알고리즘은 다음과 같음.
  • ① 입력 배열 A가 2개 이상의 원소를 가지고 있다면, A에 분할 연산을 수행함.
    • 그러면 부분 배열 L과 R이 생성됨.
  • ② ①단계의 입력으로 L을 사용함.
  • ③ ①단계의 입력으로 R을 사용함.
• 여기에서 ②단계와 ③단계는 분할 연산 에 의해 생성된 부분 배열에 재귀적으로 적용됨.
  • 이러한 분할 연산을 재귀적으로 반복할수록, 모든 원소가 차츰 오름차순 으로 정렬됨.
• 퀵 정렬 재귀 트리(Recursion Tree) 는 빠르게 깊은 형태로 구성될 수 있음.

• 입력 배열이 어떤 순서로 되어 있는지를 알 수 없기 때문에 임의의 원소를 피벗으로 선택하여 사용해도 무방 함.

 

코드

#include <iostream>
#include <vector>

template <typename T>
auto partition(typename std::vector<T>::iterator begin, typename std::vector<T>::iterator end) {
    // 3개의 반복자 생성
    // 하나는 피벗을 가리키고, 나머지 둘은 벡터의 시작과 마지막 원소를 가리킴.
    auto pivot_val = *begin;    // 벡터의 맨 앞 원소를 피벗으로 설정
    auto left_iter = begin + 1;
    auto right_iter = end;

    while (true) {
        // 벡터의 첫 번째 원소부터 시작하여 피벗보다 큰 원소 찾기
        while (*left_iter <= pivot_val && std::distance(left_iter, right_iter) > 0) {
            left_iter++;
        }

        // 벡터의 마지막 원소부터 시작하여 역순으로 피벗보다 작은 원소 찾기
        while (*right_iter > pivot_val && std::distance(left_iter, right_iter) > 0) {
            right_iter--;
        }

        // 만약 left_iter와 right_iter가 같다면 교환할 원소가 없음을 의미함.
        // 그렇지 않으면 left_iter와 right_iter가 가리키는 원소를 서로 교환함.
        if (left_iter == right_iter) {
            break;
        }
        else {
            std::iter_swap(left_iter, right_iter);
        }
    }

    if (pivot_val > *right_iter) {
        std::iter_swap(begin, right_iter);
    }

    return right_iter;
}

template <typename T>
void quick_sort(typename std::vector<T>::iterator begin, typename std::vector<T>::iterator last) {
    // 만약 벡터에 하나 이상의 원소가 있을 경우
    if (std::distance(begin, last) >= 1) {
        // 분할 작업 수행
        auto partition_iter = partition<T>(begin, last);

        // 분할 작업에 의해 생성된 벡터를 재귀적으로 정렬
        quick_sort<T>(begin, partition_iter - 1);
        quick_sort<T>(partition_iter, last);
    }
}

template <typename T>
void print_vector(std::vector<T> arr) {
    for (auto i : arr) {
        std::cout << i << " ";
    }

    std::cout << std::endl;
}

void run_quick_sort_test() {
    std::vector<int> S1 {45, 1, 3, 1, 2, 3, 45, 5, 1, 2, 44, 5, 7};
    std::vector<float> S2 {45.6f, 1.0f, 3.8f, 1.01f, 2.2f, 3.9f, 45.3f, 5.5f, 1.0f, 2.0f, 44.0f, 5.0f, 7.0f};
    std::vector<double> S3 {45.6, 1.0, 3.8, 1.01, 2.2, 3.9, 45.3, 5.5, 1.0, 2.0, 44.0, 5.0, 7.0};
    std::vector<char> C {'b', 'z', 'a', 'e', 'f', 't', 'q', 'u', 'y'};

    std::cout << "정렬되지 않은 입력 벡터:" << std::endl;
    print_vector<int>(S1);
    print_vector<float>(S2);
    print_vector<double>(S3);
    print_vector<char>(C);
    std::cout << std::endl;

    // arr.end()는 맨 마지막 원소 다음을 가리키므로 arr.end() - 1 형태로 호출
    quick_sort<int>(S1.begin(), S1.end() - 1);
    quick_sort<float>(S2.begin(), S2.end() - 1);
    quick_sort<double>(S3.begin(), S3.end() - 1);
    quick_sort<char>(C.begin(), C.end() - 1);

    std::cout << "퀵 정렬에 의해 정렬된 벡터:" << std::endl;
    print_vector<int>(S1);
    print_vector<float>(S2);
    print_vector<double>(S3);
    print_vector<char>(C);
    std::cout << std::endl;
}

int main() {
    run_quick_sort_test();

    return 0;
}

 

결과

정렬되지 않은 입력 벡터:
45 1 3 1 2 3 45 5 1 2 44 5 7
45.6 1 3.8 1.01 2.2 3.9 45.3 5.5 1 2 44 5 7 
45.6 1 3.8 1.01 2.2 3.9 45.3 5.5 1 2 44 5 7 
b z a e f t q u y

퀵 정렬에 의해 정렬된 벡터:
1 1 1 2 2 3 3 5 5 7 44 45 45
1 1 1.01 2 2.2 3.8 3.9 5 5.5 7 44 45.3 45.6 
1 1 1.01 2 2.2 3.8 3.9 5 5.5 7 44 45.3 45.6 
a b e f q t u y z