template <class T>
void QuickSort(T *a, const int left, const int right)
{
// Sort a[left:right] into nondecreasing order.
// a[left] is arbitrarily chosen as the pivot. Variables i and j
// are used to partition the subarray so that at any time a[m] ≤ pivot, m < i
// and a[m] ≥ pivot, m > j. It is assumed that a[left] ≤ a[right + 1]
if (left < right) {
int i=left,
j = right + 1,
pivot = a[left];
do {
do i++; while (a[i] < pivot);
do j--; while (a[j] > pivot);
if(i < j) swap(a[i], a[j]);
} while (i<j);
swap(a[left], a[j]);
QuickSort(a, left, j-1);
QuickSort(a, j+1, right);
}
}
- 재귀 호출이 partition 작업이 끝난 후에야 수행되는 것을 볼 수 있다.
- partition이 In-place 방식이다.
