How quicksort divides and conquers
Follow pivot selection, partitioning, and recursion, and compare average and worst-case complexity.
Read the Korean original on Velog ↗English translation
The interesting part of quicksort is how one pivot turns a large problem into smaller ones. Each partition follows the same rule until the array is sorted.
Quicksort
Quicksort partitions an array around a pivot and recursively sorts the resulting parts. Its average time complexity is O(n log n), while the worst case is O(n^2). Its strong average performance makes it a widely used sorting approach.
Divide and conquer
Divide a problem into smaller subproblems, solve them recursively, then use those results to solve the original problem.
Recursion A recursive function calls itself to solve a smaller version of the same problem.
The process
- Choose an element as the pivot.
- Partition the array so smaller elements are on one side and larger elements on the other.
- Recursively sort the left and right partitions.
- Stop when a partition contains at most one element.
- The sorted left partition, pivot, and sorted right partition form the final order.
