- 파티션 함수를 통해 '피벗값'을 정한다.
여기서 파티션 함수의 수행은 이러하다
1. 피벗값을 중심으로 왼쪽에는 피벗보다 작은 값을, 오른쪽에는 피벗보다 큰 값을 정렬한다.
2. 이를위해 left와 right이 배열을 따라 내려오면서, arr[left] > pivot 인경우와 arr[right]<pivot인 경우
서로 스왑해준다.
3. 이를 반복하다가 left > right 이 되는 경우, 즉 right과 left가 서로 교차하는 경우 루프를 멈추어준다.
4. 멈춘 곳에서 right과 우리가 정한 pivot의 자리를 바꾸어준다. 왜냐하면, pivot을 맨 첫번째 요소로 선택한다 했을때, pivot은 자신보다 작은 값과 바꾸어 져야하는데 pivot보다 작은 값을 마지막으로 가리키고 있는 것은 right이기 때문이다.
즉,pivot값 <pivot보다 작은 값 j> <i 피벗보다 큰 값> 이렇게 위치해있으므로 둘을 바꾸어주는 게맞다.
5. 따라서 right자리에 pivot이 들어가므로 right을 피벗값으로 리턴해준다.
- 반환된 피벗값의 인덱스를 중심으로 배열을 나누어 반복한다. 해당 피벗자리는 이미 정렬되었으므로, 피벗자리를 중심으로 앞, 뒤 배열을 나누어준다
- 이 과정을 배열을 더이상 나눌 수 없을 때까지 계속한다.
- 퀵소트 역시, 분할정복으로 재귀함수의 깊이가 O(log2N)이다. 또한 재귀마다 실행되는 파티션 내부에서 비교 및 교환 연산이 평균적으로 N번 수행되기 때문에 O(Nlog2N)이라고 할 수 있다.
- 하지만, 이러한 일반 퀵소트의 경우 피벗값의 선정이 문제가 될 수 있다. 특히나 피벗값을 맨 앞 값이나 맨 뒷값으로 선정했는데, 배열이 이미 정렬된 경우에는 재귀의 깊이가 N까지 가게 된다. 여기에 파티션에서의 연산이 재귀마다 N번 수행된다고 했을 때 최악의 경우 (이미 정렬된 배열) 에 퀵소트의 시간복잡도는 O(N^2)이다.
#include <iostream>
using namespace std;
void swap(int arr[], int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
int partition(int arr[], int first, int last) {
int pivot = arr[first];
//들어가서 먼저 ++ -- 될 것이므로..
int i = first ;
int j = last+1;
while (1) {
while (++i < last && arr[front] < pivot); //첫번째 조건식은 ++i < j 로 바꿔도 무방하다
//어차피 두번째 조건식때문에 루프가 멈추는 경우는 i<j이기 때문에
while (--j> first >= front && arr[rear] > pivot);
//rear >= front 인 경우도 루프 돌아가도록 처리해야함 -> 그래야지 언젠가 rear와 front가 엇갈린다.
if (front < rear) swap(arr, front, rear);
if (rear <front) break;
}
swap(arr, first, rear);
return rear;
}
void Quick_sort(int arr[], int first, int last) {
if(first<last)
{
int q = partition(arr, first, last);
Quick_sort(arr, first, q-1); //인덱스 q는 이미 정렬되었음. q를 기준으로 양옆값 보기.
Quick_sort(arr, q + 1, first);
}
}