개념 요약
- 분할 정복을 통해 주어진 배열을 정렬한다.
- 분할 정복 : 문제를 2개의 문제로 분리하여 각각 해결하고 결과를 모아서 해결하는 전략이다.
- 분리할 때 비 균등하게 분할하여 해결한다.
정렬 과정
- 배열 내의 하나의 원소를 고른다.(pivot을 고름)
- pivot보다 작으면 pivot의 앞으로, pivot보다 크면 pivot의 뒤로 분리한다.
- 1 -> 2의 과정을 분리된 상태에서 재귀적으로 반복한다.
코드
void quick_sort(std::vector<int> &unsorted_array, int left, int right)
{
//왼쪽값이 오른쪽 값보다 크다면 끝
if (left >= right)
return ;
// 피봇과 왼쪽 인덱스 저장
int i = left, j = left, temp = 0;
int &pivot = unsorted_array[right];
// 오른쪽 인덱스까지 루프
for (; j < right; ++j)
{
// 피봇보다 작다면 swap
if (unsorted_array[j] < pivot)
{
temp = unsorted_array[i];
unsorted_array[i] = unsorted_array[j];
unsorted_array[j] = temp;
++i;
}
}
// 피폿 교체
temp = unsorted_array[i];
unsorted_array[i] = pivot;
pivot = temp;
// 재귀
quick_sort(unsorted_array, left, i - 1);
quick_sort(unsorted_array, i + 1, right);
}
시간 복잡도
- 피봇을 매번 중간값을 잡은 경우(최선의 경우)에 $O(nlog_2n)$이다.
- 배열이 이미 오름차순 또는 내림차순으로 정렬되어있는 경우 $O(n^2)$이다.
공간 복잡도
- 주어진 배열 내에서 swap으로 정렬하므로 $O(n)$이다.
장단점
- 불필요한 데이터의 이동을 줄이고, 한번 결정된 피벗을 제외하기 때문에 동일 시간 복잡도를 가진 다른 정렬보다 빠르다.
- 불안정 정렬이며 이미 정렬돼있다면 오히려 비효율적이다.