퀵정렬 구현하기, C++

퀵정렬도 분할 정복을 이용한 정렬로

병합정렬에서 조금 더 조건이 추가된 정렬이라고 보면 된다.

또한 병합정렬이 대량의 데이터를 대상으로 한다면

퀵정렬은 빠른 시간을 위한 정렬이다.

 

그렇다면 무엇이 다르냐?

피벗이 있다는 것이다.

주어진 배열을 부분 배열로 나누고 각 부분 배열을 정렬하여 합치는 것과 같다. 

??? 엥 그럼 피벗은 어디다 쓰는거야???

 

피벗은 주어진 부분 배열을 나누는데 쓰이고 부분 배열을 정리하는데 쓰인다. 

구현해보자

#include <iostream>
#include <vector>


//분할하는 작업
template <typename T>
auto partition(typename std::vector<T>::iterator begin, typename std::vector<T>::iterator end)
{
    //3개의 반복자를 사용한다.
    //1. 피벗, 2. 벡터의 시작, 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와 right가 만났다는 말은 교환할 원소가 없다는 말이다.
        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);
        
    //결국 분할된 것들 중 오른쪽으로 분할된 iterator를 반환
    return right_iter;
}

//이젠 정렬함수
template <typename T>
void quick_sort(typename std::vector<T>::iterator begin, typename std::vector<T>::iterator last)
{
    //정렬하려는 벡터의 원소 체크(1개 이상)
    if(std::distance(begin, last) >= 1)
    {
        //분할
        auto partition_iter = partition<T>(begin, last);
        
        //분할 작업 후 재귀적으로 정렬
        quick_sort<T>(begin, partition_iter - 1);
        
        quicksort<T>(partition_iter, last);
        
    }
}

 

퀵 정렬을 알고리즘을 조금 더 알아보자

 

분할 부분부터 알아보자

우선 입력된 배열을 2개의 배열로 분할한다. (L, R)

**분할하기 위해서는 입력 배열에 2개 이상의 원소가 있어야 한다.

이 2개의 배열은 피벗을 기준으로 작은 쪽과 큰 쪽을 담은 배열이다.

입력 배열을 다시 피봇과 함께 재구성한다.

L P R로 만든다.

 

요약하면 분할 -> 정렬 -> 재구성이다.

 

정렬은 분할 후에 일어난다.