The Quick Guide to Understanding Quicksort
Quicksort is one of the most popular algorithms to sort with. It’s average use case is great, it’s relatively easy to implement, and it’s worst case isn’t that easy to stumble into. We’ll go over how it’s actually implemented and what can be done better with it.
Introducing Quicksort
Quicksort is a divide and conquer algorithm. It works by splitting the data set into increasingly smaller sets and recursively iterating over them until there’s nothing left. It tends towards O( n log n ) but can be in the worst scenarios.
Quicksort uses this basic process in order to sort:
1. Pick a pivot
2. Partition the array into 3 subarrays: A. items < pivot, B. the pivot, C. items >= pivot
3. Recursively quicksort A and C
Picking a Pivot
For the sake of simplicity, most implementation examples just use the leftmost or rightmost element. This obviously isn’t always efficient or desirable, but is easy as a good jumping off point. Many implementations use a random pivot somewhere in the array. We won’t really get into the pros and cons of our initial pivot at this point.
