퀵 정렬

퀵 정렬은 임의의 원소를 피벗으로 하여, 피벗과 비교하여 작은 값이 모인 집합과 큰 값이 모인 집합 두개로 나눕니다. 그 후 만들어진 두 집합 역시 동일한 과정을 거쳐 원소를 하나만 가질때까지 반복합니다. 퀵 정렬은 최악의 경우 $O(N)$의 시간 복잡도를 가지게 되는 데, 그럼에도 병합정렬이 아닌 퀵 정렬을 사용하는 이유는 평균 시간 복잡도는 $O(nlogn)$으로 병합 정렬보다 빠르기 때문입니다. 또한 추가적인 메모리를 필요로하지 않고, 입력 배열 자체를 정렬하는 제자리 정렬 알고리즘입니다.

다음은 퀵 정렬의 코드입니다.

#include <iostream>
#include <vector>
using namespace std;
 
template<typename T>
auto partition(typename vector<T>::iterator begin, typename vector<T>::iterator end)
{
    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--;
        if(right_iter==left_iter)
            break;
        else
            iter_swap(left_iter, right_iter);
        
    }
    if(pivot_val>*right_iter)
        iter_swap(begin, right_iter);
 
    return right_iter;
}
 
template<typename T>
void quick_sort(typename vector<T>::iterator begin, typename vector<T>::iterator end)
{
    if(distance(begin, end)>=1)
    {
        auto partition_iter = partition<T>(begin, end);
        quick_sort<T>(begin, partition_iter-1);
        quick_sort<T>(partition_iter,end);
    }
}
 
template<typename T>
void print_vector(vector<T> arr)
{
	for (auto i : arr)
		cout << i << " ";
	cout << endl;
}
 
void run_quick_sort_test()
{
	vector<int>	S1{ 45, 1, 3, 1, 2, 3, 45, 5, 1, 2, 44, 5, 7 };
	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 };
	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 };
	vector<char>	S4{ 'b', 'z', 'a', 'e', 'f', 't', 'q', 'u', 'y'};
 
	cout << "정렬되지 않은 입력 벡터:" << endl;
	print_vector<int>(S1);
	print_vector<float>(S2);
	print_vector<double>(S3);
	print_vector<char>(S4);
	cout << endl;
 
	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>(S4.begin(),S4.end()-1);
 
	cout << "퀵 정합에 의해 정렬된 벡터:" << endl;
	print_vector<int>(S1);
	print_vector<float>(S2);
	print_vector<double>(S3);
	print_vector<char>(S4);
	cout << endl;
}
 
int main()
{
	run_quick_sort_test();
	return 0;
}

각각의 함수에 대한 간단한 설명을 하겠습니다.
1. auto partition(typename vector<T>::iterator begin, typename vector<T>::iterator end)
해당 함수는 전달인자로 배열의 시작 주소와 마지막 주소를 받습니다. 그 후 첫 번째 주소에 저장된 원소를 피벗으로 두고, 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 배치하고 반환 값으로는 피벗보다 큰 원소의 주소를 반환합니다.

2. void quick_sort(typename vector<T>::iterator begin, typename vector<T>::iterator end)
해당 함수는 partition함수를 사용하여 얻은 원소를 기준으로 배열을 두개로 나누는 과정을 배열의 원소가 하나가 될 때까지 반복합니다.

이해를 돕기 위해 예시를 보겠습니다.

45	1	3	1	2	3	45	5	1	2	44	5	7

퀵 정렬은 임의의 원소값을 기준으로 나누지만 해당 코드에서는 첫 번째 원소를 기준으로 배열을 분리 했기에 그를 따르도록 하겠습니다.(피벗은 파랑색)

1	3	1	2	3	45	5	1	2	44	5	7	/	45

---

1	/	1	1	/	3	2	3	45	5	2	44	5	7	/	45

---

1	/	1	/	1	/	2	3	2	3	/	45	5	44	5	7	/	45

---

1	/	1	/	1	/	2	2	/	3	3	/	5	44	5	7	/	45	/	45

---

1	/	1	/	1	/	2	/	2	/	3	/	3	/	5	5	/	45	7	/	45	/	45

---

1	/	1	/	1	/	2	/	2	/	3	/	3	/	5	/	5	/	7	/	45	/	45	/	45

---

위에서 보듯 운이 좋지않다면, 단 하나의 값만을 정렬하는 좋지 못한 모습도 보인다.
이 경우(최악의 경우)에는 시간복잡도는 $n^2$이 될 것입니다.

알고리즘	최선의 경우	평균	최악의 경우
병합 정렬	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$
퀵 정렬	$O(nlogn)$	$O(nlogn)$	$O(n^2)$