Sort an array in increasing order, in place. Quick sort is one of the fastest sorts in practice.
DSA Animator › DSA Revision › Sorting Algorithms › Quick Sort
Remember: partition puts the pivot in its final place. Choose pivots well to avoid the quadratic worst case. The video solves Quick Sort (LeetCode 912, Medium) with the Partition + Recursion pattern from the Sorting Algorithms topic, and you can replay every step in the interactive Quick Sort animation.
Sort an array in increasing order, in place. Quick sort is one of the fastest sorts in practice.
For 7, 2, 9, 4, 3, 8, 5, the result is 2, 3, 4, 5, 7, 8, 9.
Simple sorts compare almost every pair, which is O of n squared. Quick sort divides the problem instead.
Pick a pivot, here the last element. Partition: move everything smaller than the pivot to the left side. Then put the pivot right after them, which is its final sorted position. Now sort the left part and the right part recursively. Each partition is one linear scan.
The pivot is 5, and the scan finds 2, 4 and 3 as smaller values. They move to the front, and 5 lands at index 3, giving 2, 4, 3, 5, 9, 8, 7. The left part 2, 4, 3 uses pivot 3, which gives 2, 3, 4. The right part 9, 8, 7 uses pivot 7, which lands at index 4. Then 8, 9 with pivot 9 is already in order. The array is 2, 3, 4, 5, 7, 8, 9.
In code, quick sort calls partition, then recurses on both sides. Partition keeps an index i for the next small slot, and scans j from low to high minus 1. When a of j is smaller than the pivot, swap it into slot i and move i. Finally swap the pivot into slot i, and return i. It's O of n log n on average, but O of n squared on bad pivots, so random pivots are common.
Remember: partition puts the pivot in its final place. Choose pivots well to avoid the quadratic worst case.