Quick Sort
Is a divide and conquer sorting algorithm re-using the core idea of transitivity from binary-search.
Formulation
def quick_sort(arr, beg, end):
if beg < end:
p = partition(arr, beg, end)
quick_sort(arr, beg, p - 1)
quick_sort(arr, p + 1, end)
def partition(beg, end, arr):
"""Partition all the elements of ARR such that ARR[END] is
at its correct position and all the elements smaller than
ARR[END] is below this position and all elements larger are
after this position.
Returns
-------
The position at which the partition was made.
"""
pivot = arr[end]
i = beg
for j in range(beg, end):
if a[j] < pivot:
swap(arr, i, j)
i += 1
swap(arr, i, end)
return i
quick_sort(arr, 0, len(arr) - 1)You can see the quick-sort algorithm in alg:quick-sort. The main [see page 3, idea] behind the algorithm is to place one element in its correct position, partitioning all elements smaller than it to lower positions and all those larger than it to larger positions, and then recursively applying the same process to the partitioned sub-arrays. The advantage of this approach is that all the elements in the partitioned sub-arrays only need to be compared with pivot of the partition, we don't have to compare them with any other partitions. By transitivity the elements in the left partition are all less than the pivot therefore their all also less than every element in the right sub-partition. Note: For this algorithm the pivot is set to the right most element of a sub-array. It can equivalently be set to the middle element or the first element or a random element.
The partition procedure described in alg:quick-sort works in two steps.
It records the position that the pivot is supposed to go to in the variable i.
Each iteration when a value smaller than the pivot is encountered, i is
incremented and that value is moved to where i was. This has the affect of pushing
values smaller than the pivot to before i and larger than the pivot after i.
At the end of the loop we swap the pivot into where i is, placing it at the point
in the array where all the elements smaller than the pivot are before it and by
definition all the elements larger than it must be after the pivot.
Runtime Performance
The runtime-performance of quick-sort depends on [see page 10, how] the array is partitioned and therefore the choice of the pivot. Consider being given an already sorted array to sort and then choosing the pivot as the right most element just like before. In the first iteration we scan through the entire array, realise the pivot goes to the last element of the array and then recursively apply the same process to the sub-array \( 0,\ldots,(n-1) \). This happens repeatedly for the entire length of the array giving us a [see page 11, runtime] of \( \theta(n^2) \). In the [see page 12, best-case] quick-sort splits the problem into two sub-problems of size \( \lfloor \frac{n}{2} \rfloor \) and \( \lceil \frac{n}{2} \rceil - 1 \) respectively.
Assuming the array is randomly sorted we find the [see page 14, average-case] performance of quick-sort is \( \mathcal{O}(n \log n) \). Therefore the best approach is to pick the pivot [see page 16, randomly], this ensures all inputs lead to the same runtime behaviour, levelling the playing field for every input and avoiding the worst-case performance described above.
Improvements to the Classical Algorithm
Quick sort is fast in practice because of small constants in the asymptotic running time. However there's still room for [see page 15, improvements].
We can make quick sort faster when dealing with arrays of equal elements by partitioning into smaller, equal and larger sub-arrays. We can then only focus on the smaller and larger arrays reducing the runtime to \( \mathcal{O}(n) \) for equal value arrays.
We could choose the pivot as the median of 3 elements, giving better performance in practice, but worst case is still the same.
Vladimir Yaroslavskiy implemented a dual-pivot quick-sort for Java 7.