Quicksort, as its name, is one of the fastest sorting algorithms invented by Tony Hoare in 1959.
After this tutorial, I ensure you can achieve 2 things:
- Understand how the Quicksort algorithm works.
- Implement the Quicksort algorithm in Python.
Before going to the quicksort algorithm, you need to understand the divide-and-conquer paradigm.
Divide-and-conquer is used to find the optimal solution by breaking down the problem into smaller sub-problems. Then, we solve each sub-problem and combine the results to get the final solution.
The divide-and-conquer paradigm consists of 3 steps:
- Divide: Break the problem into smaller sub-problems.
- Conquer: Solve each sub-problem recursively.
- Combine: Combine the results of each sub-problem to get the final solution.
The quicksort algorithm is based on the divide-and-conquer paradigm.
The quicksort algorithm consists of 2 steps:
- Divide: Choose a pivot element* and partition the array into 2 sub-arrays: the left sub-array contains elements smaller than the pivot, and the right sub-array contains elements greater than the pivot.
- Conquer: Recursively sort the left and right sub-arrays.
*The pivot element is chosen randomly or deterministically. In this tutorial, we choose the middle element as the pivot.
Here is the implementation of the quicksort algorithm in Python: