거품, 힙 중에서 가장 빠른 알고리즘이다.
분할정복이라는 접근 방식을 이용해서 배열을 정렬하는 재귀적인 알고리즘이다.
1. 기준값 하나 선택
2. 그 기준값보다 작은 항목들을 배열의 왼쪽으로
3. 그 기준값보다 큰 항목들을 배열의 오른쪽으로
4. 왼쪽 부분 배열에 퀵 정렬을 재귀적으로 적용
5. 오른쪽 부분 배열에 퀵 정렬을 재귀적으로 적용
퀵정렬이 가장 효율적으로 작동하려면 두 부분배열들의 크기가 거의 비슷해야한다.
삼중앙 알고리즘을 쓰는데
첫 번째 중간 마지막 색인의 값들을 취해서 그 셋 중 가운데 값을 기준값으로 사용
11 10 16 4 8 12 1 6 0 20 2 9 5
이렇게 있을때 제일앞의 11 중간의 1 마지막의 5를 취하고 그중 가운데에 해당하는 5를 기준값으로 선정
기준값을 밖으로 뺀다
<5> 11 10 16 4 8 12 1 6 0 20 2 9 [ ]
그러면 빈칸이 하나 생기고 그 빈칸이 배열 제일 앞에 오게해야하니(제대로 작동되려면) 제일 앞의 11을 기준값이 있던 자리로 옮김
<5> [ ] 10 16 4 8 12 1 6 0 20 2 9 11
여기까지가 퀵 정렬에 필요한 설정이 끝남
이렇게 배열을 설정하고 앞 뒤로 여러번 훑게 된다.
우선 뒤에서 시작한다했을때 기준값보다 작은 값을 발견하면 탐색을 멈추고 그 값과 빈칸을 바꾼다.
이제 다시 반대 방향으로 훑어나가다 기준값보다 큰 값을 만나면 탐색을 멈추고 그 값을 빈칸과 바꾼다.
이 과정을 계속 반복..그리고 마지막 빈칸을 만나면 그곳에 기준값(여기선 5를 넣는다)
<- 진행방향
<5> [ ] 10 16 4 8 12 1 6 0 20 2 9 11
<5> 2 10 16 4 8 12 1 6 0 20 [ ] 9 11
-> 진행방향
<5> 2 [ ] 16 4 8 12 1 6 0 20 10 9 11
계속하다가 빈칸을 좌측이던 우측이던 만나면 빈칸에 기준값을 넣는다!
<5> 2 0 1 4 [ ] 12 8 6 16 20 10 9 11
2 0 1 4 5 12 8 6 16 20 10 9 11
그런 다음에 좌, 우 두 부분배열에 대해 각각 퀵정렬을 적용한다.
먼저 왼쪽 부분 배열에 퀵 정렬을 적용하면
2 0 1 4
첫번째 2 마지막 4 중간 0
기준값 2로 선정
<2> [ ] 0 1 4
<- 진행방향
<2> [ ] 0 1 4
<2> 1 0 [ ] 4
-> 진행방향
<2> 1 0 [ ] 4
빈칸 만났으니..
<2> 1 0 [ ] 4
1 0 2 4
짠 정렬!
퀵 정렬 역시 최악의 경우 N^2이지만 상중앙 알고리즘 선택기법을 활용하면 O (n log2 n)
아래는 중간값을 얻기위한 함수
template
int FindMedianOfThree(Array& p_array, int p_first, int p_size, int(*p_compare)(Datatype, Datatype))
{
int last = p_first + p_size - 1;
int mid = p_first + (p_size / 2);
if (p_compare(p_array[p_first], p_array[mid]) < 0 && p_compare(p_array[p_first], p_array[last] < 0))
{
if (p_compare(p_array[mid], p_array[last]) < 0)
{
return mid;
}
else
{
return last;
}
}
if (p_compare(p_array[mid], p_array[p_first] < 0 && p_compare(p_array[mid], p_array[last]) < 0))
{
if (p_compare(p_array[p_first], p_array[last] < 0))
{
return p_first;
}
else
{
return last;
}
}
if (p_compare(p_array[p_first], p_array[last]) < 0)
{
return p_first;
}
return mid;
}
아래는 퀵 정렬 함수
template
void QuickSort(Array& p_array, int p_first, int p_size, int(*p_compare)(DataType, DataType))
{
int pivot;
int last = p_first + p_size - 1;
int mid;
int lower = p_first; //하한 색인 즉 왼쪽에서 오른쪽으로 탐색방향
int higher = last; //상한 색인 즉 오른쪽에서 왼쪽으로 탐색방향
if (p_size > 1)
{
mid = FindMedianOfThree(p_array, p_first, p_size, p_compare);
pivot = p_array[mid];
p_array[mid] = p_array[p_first];
while (lower < higher)
{
//상한 색인에서 시작해서 앞쪽으로 칸들을 훑다가 기준값보다 작은 값을 발견하거나
//하한 색인에 도달하면 멈춤다
while (p_compare(pivot, p_array[higher]) < 0 && lower < higher)
higher--; //찾는거에 따라 higher값이 내려간다 점점..나중에 거기서부터 시작하려고..
if (higher != lower)
{
p_array[lower] = p_array[higher];
lower++; //값을 넣고 증가, 어차피 증가안하면 그 값은 정렬된 값이라 재검색하면 불필요하잖아..
}
while (p_compare(pivot, p_array[lower])>0 && lower < higher)
lower--; //이젠 반대로 간다
if (higher != lower)
{
p_array[higher] = p_array[lower]; //higher에 넣어도 되는 이유가 위에서 이미 higher값은 lower로 옮겨갔다, 즉 빈칸
higher--;
}
}
p_array[lower] = pivot; //왜 lower에 넣느냐 higher가 아니라 while의 조건자체가 lower < higher이니까
//아래는 왼쪽도 또해야하고 오른쪽도 또해야하니까 재귀함수
QuickSort(p_array, p_first, lower-p_first, p_compare);
QuickSort(p_array, lower + 1, last - lower, p_compare);
}
}