Quicksort

More notes coming soon!

Quicksort is a recursive sorting algorithm that is defined as follows:
- Partition on some pivot.
  
  (After partitioning, the pivot element will be in the correct position.)
- Quicksort to the left of the pivot.
- Quicksort to the right of the pivot.
Just as merge sort, quicksort is a recursive divide-and-conquer algorithm. However, unlike merge sort that does all the work at the end (the “conquer” step), quicksort does all the work at the beginning (the “divide” step).

Partitioning

Partioning an array on a pivot means to rearrange the array such that all items to the left of the pivot are ≤ the pivot, and all items to the right are ≥ the pivot. Naturally, the pivot can move during this process.

For example, if we wanted to partition this array on 10.

5

550

10

4

10

9

330

These partitions would be valid.

4

5

9

10

330

10

550

5

9

10

4

10

4

550

5

4

9

10

10

550

330

But this one would be invalid.

5

9

10

4

10

550

330
There many ways to do partitions. Notice that after we partition on a pivot, that pivot will end up in the correct position according to the sorted order.

It is possible to partition an array on a pivot in linear time using constant space:
- Put pivot at position 0 (by swapping the pivot element with the element at position 0).
- Create L and G pointers at left and right ends
- L pointer is a friend to small items and hates large or equal items
- G pointer is a friend to large items and hates small or equal items
- Repeat until pointers cross:
  - Walk pointers toward each other stopping on hated items
  - When pointers have stopped, swap items and move pointers by one
- Swap pivot and element pointed to by G
We can also put the pivot at the last position in the array. Then, at the end of the partitioning, we will have to swap pivot and the element point to by L (not G).

Ideally, after partitioning the pivot would be in the middle of the array and we are left with two subarrays of equal size. To do so would mean that we must always select the meadian as the pivot. While it is possible to find the median in an unsorted array of size $n$ in $O(n \log n)$ or even in constant time^[1]^[2], it is never efficient enough in practice.
If we always select the same element, such as the first element, the last element, or the middle element, we risk having input that will cause the pivot to move to one side of the array and the subarray either at the left side or at the right side of the array to be empty. In other words, there can always be input that will prevent the problem from getting split into (relatively) equal halves and will degrade the quicksort algorithm to quadratic time complexity.
Therefore, the best strategy for selecting the pivot is to either choose a random element in the array or to shuffle the array before partitioning (and then select the first element for example). It is very, very unlikely that over a sequence of partitioning operations during quicksort, we will get poor selections of pivots.

TODO

In the best case, Quicksort has runtime $\Theta(N \log N)$ , and in the worse case has runtime $\Theta(N^2)$ .
Choice of partitioning strategy and pivot have profound impacts on runtime. Always picking the leftmost or the rightmost pivot can lead to bad performance on real data. On the other pack, by picking a random pivot or shuffling an array before sorting (using an appropriate partitioning strategy) we can ensure that Quicksort, with high probability, has an average runtime of $\Theta(N \log N)$ .
For most typical situations, Quicksort is the fastest sort.