Can sorting be faster than you think?
Quicksort
Can sorting be faster than you think?
Imagine you're organizing a bookshelf with thousands of books. Finding the quickest way to sort them by height without moving too many books around is crucial.
Quicksort picks a book as a 'pivot' and sorts the rest into shorter and taller piles, then sorts those piles themselves. This process repeats until all books are sorted.
Example
You have 100 books. Pick one as a pivot, and you end up with 49 shorter and 51 taller piles. Sort those piles, and you're closer to a sorted shelf.
Remember this
Quicksort's average-case speed is O(n log n), making it efficient for large collections.
Text adapted from Wikipedia, licensed under CC BY-SA 4.0.
Related concepts
O(n log n) is the lower bound for comparison-based sorting
Ever wonder why sorting can't be faster than a certain point?
merge sort: O(n log n) always
Ever wondered why sorting your music library takes ages?
Best, worst and average case
Quicksort's average time complexity is O(n log n)
Binary search
How fast can you find a word in a dictionary?
Hash table
Hash table lookup: O(1) average time complexity
Dijkstra's algorithm
Dijkstra's algorithm time complexity: O((V+E) log V)
Swipe through 100 ML concepts daily
Open Pocket Polymath