퀵 정렬은 임의의 원소를 피벗으로 하여, 피벗과 비교하여 작은 값이 모인 집합과 큰 값이 모인 집합 두개로 나눕니다. 그 후 만들어진 두 집합 역시 동일한 과정을 거쳐 원소를 하나만 가질때까지 반복합니다.
퀵 정렬은 최악의 경우 \(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 |
/ |
| -- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
-- |
- |
| *** |
|
|
|
|
|
|
|
|
|
|
|
|
| 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)\) |