This article is made for those who did not intuitively understand about Quick Sort while they were able to easily understand Bubble, Selection, Insertion and Merge Sort.
Although Java and Python uses a Merge Sort based TimSort, QuickSort is said to be the really efficient if implemented well.
Quick Sort shares the concept of Divide and Conquer paradigm with Merge Sort, though much of the work is done while dividing/partitioning the list (unlike merge sort , where combining is logic heavy!)
Quick Sort involves the following steps:-
- Partition the list based on the pivot (chosen by some logic) to give two sub-list.
- Call Quick Sort method recursively on both the sub-lists.
With the above information if you are able to go ahead and code, voila! you are ready to give interviews to FAANG and you can skip the following section.
For those noobs like me who have no/little clue on how to implement, please continue reading!
Let’s take an example of an array
arr = [5,4,3,6,2,7,1,8,10]
Step-1 | Partition the List:
Partition the list is basically breaking the list into 2 sublists. Since a list is divided recursively at every step till it becomes a list of size 1, the time complexity of the algorithm at average case in nlog(n).
Partition involves two steps:-
a. Choose a Pivot Index
b. Partition the list into 2 sublists using the pivot
a. Choose a Pivot Index:
There are various methods implemented to choose a pivot. Some of them choose :-
- Random element
- First index element
- Last index element
- Middle element
- 3 elements at random and take a median of those elements
For Simplicity let’s take the mid-point element(or random number) and return its index.
so in our case:-
arr = [5,4,3,6,2,7,1,8,10]
left_idx = 0
right_idx = len(arr)-1
pivot = (left_idx + right_idx)//2
b. Partition the list into 2 sublists using the Pivot:
This is the most important step of the implementation. Now that you got the pivot element from the previous step, rearrange the list in such a way that first half of the list has numbers that are less than the pivot and the second half of the list that are greater than the pivot.
For example, in our case the pivot index (midpoint) is 4 (array size is 9).
The Pivot element (at index 4 ) is 2.
- Take 2 pointers left and right such that ->left = first index (0), right = last index (length of list-1 as index starts with 0)
- Check if the left pointer is less than pivot (2). If yes, increment the left index by 1 and check if the element in the incremented left index (now left index +1) is less than pivot and so on. You can use a while loop to do this and this loop breaks if any element at the left index fails the condition.
- For right pointer, check the same way like left but for the condition -> if right index element is greater than the pivot. Also decrement the right index(instead of increment used in left pointer).
4. The above steps are basically using 2 pointers that start at the first and last element and meet at some point. Now check whether they have met. If yes, then return the partition idx (left_idx). This partition index is used to divide the list at the partition index. Because of the logic 2 & 3, usually the pivot is the index.
5. If they have not met, then it means some left or right element that is greater than or less than the pivot exists. That element’s index is captured by the steps 2 & 3. So swap that right/left element with left/right index.
pivot_idx = choose_pivot_index(arr,left_idx,right_idx)
pivot = arr[pivot_idx]
left_idx -= 1
right_idx += 1
while arr[left_idx] < pivot:
while arr[right_idx] > pivot:
# return the index by which the list is divided into 2.
# Since the elements are rearranged based on pivot, this
# index will contain the pivot element
result of the first partition
# result of the first partition all elements using 2 as pivot[1, 2, 3, 4, 6, 7, 5, 8, 10]
You can see that all elements to right of point 2 is greater than 2 and all points left of 2 is less than 2.
Now this entire partition steps run on while loop which will break eventually on the left and right index meeting at certain point.
Step-2 | Call Quick Sort recursively on both the sub-lists
Get the partition index and divide the list based on that index and recursively call the quick sort method. Now the the sublists are further divided based on the pivot chosen at the respective steps so that they are rearranged during partitioning.
if left_idx < right_idx:
# at the end of partition the index returned will be having
# the pivot element because of the partition logic
pivot_idx = partition_list(arr,left_idx,right_idx)
The final array will be a sorted array.
[1, 2, 3, 4, 5, 6, 7, 8, 10]
Although QuickSort is efficient, it can perform worse at O(n²) if the list is already sorted or contains repetition of same element.
Try to implement yourself and check with the code below:
Stay tuned for more posts on Algorithms