Understanding quicksort algorithm
The strategy from the earlier example could be used to create an algorithm. To explain this algorithm, we will take an array as an input list, but the same algorithm can be applied to any list data structure.
Algorithm
The quicksort algorithm operates on an input array containing at least two elements. The process begins by selecting a pivot element from the array, which serves as a reference point for partitioning the other elements.
Select a random element as the pivot
Next, the array is partitioned into two consecutive subarrays: one containing all elements smaller than the pivot on the left, and the other containing all elements greater than the pivot on the right. At this stage, the pivot is already in its final correct position in the sorted array.
Smaller elements go left, larger elements go right
After partitioning, quicksort recursively applies the same procedure to each subarray. This process continues until all subarrays contain only a single element or are empty.
Repeat the process on the left and right subarray with new pivots
Liking the course? Check our discounted plans to continue learning.