Overview/Implementation of Quick Sort
In this article, I will be talking about quick sort & all the components that you need to know.
Quicksort is nothing but another algorithm to sort a list of items in ascending or descending order. To understand quick sort, we need to understand the following items:
- pivot
- how partition works
- recursion within quick sort & the base case
Let’s start with pivot. What is pivot then?
Pivot is the element that will be used to divide the list of values less than pivot to the left(or the right, if we are sorting it the other direction) and values greater than the pivot to the right of the pivot.
Let’s say we have the following:
If 3 is chosen as the pivot, it will always land at where it should be left after a partition. In this case, that would be the 2nd index of the array.
To further demonstrate how that would work, view the following illustration:
On the illustration above, we have i, j, and the pivot. 4 is used as the pivot. i, initially, is set to -1. This indicates the number of elements we have that are less than the pivot. j, on the other hand, is used as an index to traverse through every element.
In partition, for every element j, if the pivot is great than arr[j], increment i and swap arr[i] and arr[j]. This will help put whatever element less than pivot on the left side of the array. J will increment regardless.
After the whole array is done, i equates to the number of elements that are less the pivot. Increment i by 1 and swap arr[i] with the pivot. Now the pivot is truly the dividing point between elements greater than it to the right and elements lesser than it to the left.
Afterward, quicksort will be called on the subarray to the left of the pivot and also to the right of the pivot. This process will repeat until there are no more subarrays to be sorted.
Here is how partition looks like:
And here is how the quicksort function looks like:
Earlier I mentioned the base case and recursion about quicksort. The base case would be if the low is not less than high, indicating there are no more elements to sort. In this case, you might be in a recursion call where you are only sorting one element left after diverging into a great number of recursive calls for quicksort.
The recursion, in this case, would be calling quick sort continuously on subarrays until there are no more elements to sort.
If you are still confused you can view the following youtube video for animation reference:
In term of performance, quicksort is o(n log n) on average and o(n²) in the worst-case scenario. Its space complexity is o(logn).
And here is my amen to keep your array all clean and great looking with quicksort.
Happy coding, folks.
