a best-case O(n log n) algorithm that has a lower space complexity (in-place sort), and is more suitable for sorting large datasets
solution:
- choose an item to be the pivot
- move all elements < pivot to the left, and all elements > pivot to the right — ‘partitioning’
- perform a swap such that the pivot is now in the middle
- recursively repeat on each half… until everything is sorted
note: quicksort can also be implemented iteratively using a stack
the ‘partitioning’ step
- have a index/pointer $i$ and $j$ point at the
lo
and hi
respectively
- so long as $i$ < pivot and $j$ > pivot, move them towards each other
- if one fails to satisfy the condition, keep moving the other one until both fail, then swap (thus fixing both of their positions)
- repeat steps 2-3 until $i$ and $j$ point to the same index
❗quicksort is not stable, but it can be if the implementation is changed (but uses more memory)