❖ Quicksort |
We can do better ...
Quicksort: basic idea
Previous sorts were all O(nk) (where k>1).
❖ Quicksort Implementation |
Elegant recursive solution ...
void quicksort(Item a[], int lo, int hi)
{
int i; // index of pivot
if (hi <= lo) return;
i = partition(a, lo, hi);
quicksort(a, lo, i-1);
quicksort(a, i+1, hi);
}
❖ ... Quicksort Implementation |
Partition implementation:
int partition(Item a[], int lo, int hi)
{
Item v = a[lo]; // pivot
int i = lo+1, j = hi;
for (;;) {
while (less(a[i],v) && i < j) i++;
while (less(v,a[j]) && j > i) j--;
if (i == j) break;
swap(a,i,j);
}
j = less(a[i],v) ? i : i-1;
swap(a,lo,j);
return j;
}
❖ Quicksort Performance |
Best case: O(nlogn) comparisons
❖ Quicksort Improvements |
Choice of pivot can have significant effect:
❖ ... Quicksort Improvements |
Median-of-three partitioning:
void medianOfThree(Item a[], int lo, int hi) { int mid = (lo+hi)/2; if (less(a[mid],a[lo])) swap(a, lo, mid); if (less(a[hi],a[mid])) swap(a, mid, hi); if (less(a[mid],a[lo])) swap(a, lo, mid); // now, we have a[lo] < a[mid] < a[hi] // swap a[mid] to a[lo+1] to use as pivot swap(a, mid, lo+1); } void quicksort(Item a[], int lo, int hi) { if (hi <= lo) return; medianOfThree(a, lo, hi); int i = partition(a, lo+1, hi-1); quicksort(a, lo, i-1); quicksort(a, i+1, hi); }
❖ ... Quicksort Improvements |
Another source of inefficiency:
❖ ... Quicksort Improvements |
Quicksort with thresholding ...
void quicksort(Item a[], int lo, int hi) { if (hi-lo < Threshhold) { insertionSort(a, lo, hi); return; } medianOfThree(a, lo, hi); int i = partition(a, lo+1, hi-1); quicksort(a, lo, i-1); quicksort(a, i+1, hi); }
❖ ... Quicksort Improvements |
If the array contains many duplicate keys
❖ Non-recursive Quicksort |
Quicksort can be implemented using an explicit stack:
void quicksortStack (Item a[], int lo, int hi) { Stack s = newStack(); StackPush(s,hi); StackPush(s,lo); while (!StackEmpty(s)) { lo = StackPop(s); hi = StackPop(s); if (hi > lo) { int i = partition (a,lo,hi); StackPush(s,hi); StackPush(s,i+1); StackPush(s,i-1); StackPush(s,lo); } } }
Produced: 20 Jul 2020