Quick Sort

Last updated Nov 8, 2022 Edit Source

1. Select a pivot element
2. Partition the input into 2 halves (1 that is lower than the pivot, 1 that is higher than the pivot)
   • At each partition we end up with an array that is sorted relative to the pivot (pivot is in the final position)
3. Recursively do the same for each half until we reach subarrays of 1 element.

The middle element is usually chosen as the pivot:

1. Swap mid with low, placing the pivot at the start of the array

2. If an element is smaller than the pivot: swap the position of a big element $(++lastsmall)$ with this smaller element $(i)$. (This step results in an algorithm).
3. If an element is larger or equal to the pivot: increment the index $(i)$
4. Once last index is reached: Swap the pivot position $low$ with $lastsmall$, placing the pivot in the middle

Key equality Note that when a key $x$ is equal to the pivot, we do not perform any swaps or increment the lastsmall counter; we simply treat it as it was bigger.

This means that at the end of the partition, $x$ will be placed on the right of pivot. Leaving the right subarray non-empty.

If we want the left subarray to be empty, the pivot must be $\le$ all keys. If we want the right subarray to be empty, the pivot must be $>$ all keys

This results in $O(nlogn)$ complexity

Forming a worst case array: