Quicksort is a prominent divide-and-conquer-based sorting algorithm renowned for its efficiency. Operating by selecting a pivot and partitioning the array around this pivot, Quicksort places the pivot in its correct sorted position. This technique achieves an average of nlogn comparisons for sorting n elements, making it notably swift.
The algorithm’s essence lies in its divide-and-conquer approach: it breaks down tasks into smaller subproblems, resolves them, and amalgamates the solutions. Initially, a pivot element is chosen, leading to the array’s partitioning into sub-arrays. One sub-array encompasses values less than or equal to the pivot, while the other contains values greater than it. Recursively, Quicksort sorts these sub-arrays. This partitioning and sorting continue until individual elements remain in each sub-array.
For students and professionals, understanding Quicksort’s fundamentals becomes pivotal, given its frequent examination appearances and its reputation as a rapid and efficient sorting method.
Working of Quick Sort Algorithm
Recall the list/array that had the elements – 10,8,5,15,610,8,5,15,6 in it. To sort these elements in ascending order using quick sort, let us follow the under-given steps –
Step – 1:
Select the pivot element, here for the sake of simplicity, we are selecting the rightmost element as the pivot.
Step – 2:
Rearrange the elements of the array in a way that all the elements smaller than the pivot are on its left and that all the greater ones are on the right. They need not be sorted. After the rearrangement, the array would look like this –
Here, 6 is our pivot element, and all the elements greater than itself are on the right side, while the elements smaller than the pivot is on its left side.
Now let us understand how did this rearrangement happen –
- Take two pointer variables that point to the left & right of the array (with pivot excluded). Let’s call them left & right respectively.
- Under a loop, increment the left pointer until a value greater than pivot is found. In this case, since 10 is already greater than 6, we move to step c.
- Under the same loop, increment the right pointer until a value smaller than pivot is found. Here, a value smaller than pivot is 5.
- Now since the conditions given in steps b and c are simultaneously fulfilled, swap the value at index left with the value at index right of the given array. This helps us move the elements smaller than the pivot element to the left of it, and the greater ones to the right of it.
Here, 5 & 10 are swapped. - Repeat steps b, c and d until the left index is greater than the right index.
- Here, the execution of the loop is stopped because left > right. Now, swap the value at pivot with the value at the index left or right.
We have placed 6 after 5, and before 10, 15, and 8. This way, we have placed 6 (pivot element) at such a position that elements smaller than it is on its left, and the elements greater than it is on its right. Notice that 6 is at its correct sorted position now.
Step – 3:
In this step, the sublist is divided into two parts – sublist before the pivot element, and sublist after the pivot element.
Step – 4:
Repeat the above-given steps recursively until all the elements of the array are at their correct sorted position.
The following diagram shows the working of the quick sort algorithm.
We have sorted the array using the quick sort algorithm. Let’s write some code to implement the algorithm.
Pseudocode for Quick Sort Algorithm
1. Pseudocode for Partitioning/Creating Subarrays –
//low and high are the lowest & highest index of the array/subarray respectively
function partition(array, low, high) {
// selecting the rightmost element as pivot
pivot = array[high]
//setting the left pointer to point at the lowest index initially
left = low
//setting the left pointer to point at the lowest index initially
right = high - 1;
//running a loop till left is smaller than right
while(left <= right)
//incrementing the value of left until the value at left'th
//index is smaller than pivot
while(array[left] < pivot)
left = left + 1
end while
//decrementing the value of right until the value at right'th
//index is greater than pivot
while(array[right] > pivot)
right = right - 1
end while
if(left < right)
//swapping the elements at left & right index
swap(array[left], array[right])
end if
end while
// swapping pivot with the element where left and right meet
swap(array[left], array[high])
// return the partition point
return left
end function
2. Pseudocode for Quick Sort Function
quickSort(array, low, high) {
if low < high
// since this function returns the point where the array is
//partitioned, it is used to track the subarrays/partitions in the
// array
pi = partition(array, low, high)
// recursively calling the function on left subarray
quickSort(array, low, pi - 1)
// recursively calling the function on right subarray
quickSort(array, pi + 1, high)
end if
end quicksort function
Implementation of Quick Sort
1. C Program for Quick Sort
// function to swap the elements
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// finding the partition point & rearranging the array
int partition(int array[], int low, int high) {
// selecting the rightmost element as pivot
int pivot = array[high];
//setting the left pointer to point at the lowest index initially
int left = low;
//setting the left pointer to point at the lowest index initially
int right = high - 1;
//running a loop till left is smaller than right
while(left <= right){
//incrementing the value of left until the value at left'th index is smaller than pivot
while(array[left] < pivot){
left++;
}
//decrementing the value of right until the value at right'th index is greater than pivot
while(array[right] > pivot){
right--;
}
if(left < right){
//swapping the elements at left & right index
swap(&array[left], &array[right]);
}
}
// swapping pivot with the element where left and right meet
swap(array[left], array[high]);
// return the partition point
return (left);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
// since this function returns the point where the array is partitioned, it is used to track the subarrays/partitions in the array
int pi = partition(array, low, high);
// recursively calling the function on left subarray
quickSort(array, low, pi - 1);
// recursively calling the function on right subarray
quickSort(array, pi + 1, high);
}
}
2. C++ Program for Quick Sort
// finding the partition point & rearranging the array
int partition(int array[], int low, int high) {
// selecting the rightmost element as pivot
int pivot = array[high];
//setting the left pointer to point at the lowest index initially
int left = low;
//setting the left pointer to point at the lowest index initially
int right = high - 1;
//running a loop till left is smaller than right
while(left <= right){
//incrementing the value of left until the value at left'th index is smaller than pivot
while(array[left] < pivot){
left++;
}
//decrementing the value of right until the value at right'th index is greater than pivot
while(array[right] > pivot){
right--;
}
if(left < right){
//swapping the elements at left & right index
swap(array[left], array[right]);
}
}
// swapping pivot with the element where left and right meet
swap(array[left], array[high]);
// return the partition point
return (left);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
// since this function returns the point where the array is partitioned, it is used to track the subarrays/partitions in the array
int pi = partition(array, low, high);
// recursively calling the function on left subarray
quickSort(array, low, pi - 1);
// recursively calling the function on right subarray
quickSort(array, pi + 1, high);
}
}
3. Python Program for Quick Sort
# Quick sort in Python
# finding the partition point & rearranging the array
def partition(array, low, high):
# selecting the rightmost element as pivot
pivot = array[high];
# setting the left pointer to point at the lowest index initially
left = low;
#setting the left pointer to point at the lowest index initially
right = high - 1;
#running a loop till left is smaller than right
while (left <= right):
#incrementing the value of left until the value at left'th
# index is smaller than pivot
while (array[left] < pivot):
left = left + 1
#decrementing the value of right until the value at right'th
#index is greater than pivot
while (array[right] > pivot):
right = right - 1;
if (left < right):
#swapping the elements at left & right index
array[left], array[right] = array[right], array[left]
#swapping pivot with the element where left and right meet
array[left], array[high] = array[high], array[left]
# return the partition point
return left
# function to perform quicksort
def quickSort(array, low, high):
if low < high:
# since this function returns the point where the array is
#partitioned, it is used to track the subarrays/partitions in the
#array
pi = partition(array, low, high)
# recursively calling the function on left subarray
quickSort(array, low, pi - 1)
# recursively calling the function on right subarray
quickSort(array, pi + 1, high)
4. Java Program for Quick Sort
class Quicksort {
// method to find the partition position
static int partition(int array[], int low, int high) {
// selecting the rightmost element as pivot
int pivot = array[high];
//setting the left pointer to point at the lowest index initially
int left = low;
//setting the left pointer to point at the lowest index initially
int right = high - 1;
//running a loop till left is smaller than right
while(left <= right){
//incrementing the value of left until the value at left'th
//index is smaller than pivot
while(array[left] < pivot){
left++;
}
//decrementing the value of right until the value at right'th
//index is greater than pivot
while(array[right] > pivot){
right--;
}
if(left < right){
//swapping the elements at left & right index
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
}
// swapping pivot with the element where left and right meet
int temp = array[left];
array[left] = array[high];
array[high] = temp;
// return the partition point
return (left);
}
static void quickSort(int array[], int low, int high) {
if (low < high) {
// since this function returns the point where the array is
//partitioned, it is used to track the subarrays/partitions in
//the array
int pi = partition(array, low, high);
// recursively calling the function on left subarray
quickSort(array, low, pi - 1);
// recursively calling the function on right subarray
quickSort(array, pi + 1, high);
}
}
}
Complexity Analysis of Quick Sort
1. Quick Sort Time Complexity
Best-Case:
The best-case occurs when the pivot is almost in the middle of the array, and the partitioning is done in the middle. So, let us assume that we have a total of n elements in the array, and we are dividing the array from the middle.
In this case, with each partition, we will have at most n/2 elements. And we have to perform the partition until only one element is left in each subarray. The following is the tree representation of the given condition
Notice that the above-given tree is a binary tree. And for a binary tree, we can know that its height is equal to logn. Therefore, the complexity of this part is O(logn).
Also, the time complexity of the partition() function would be equal to O(n). This is because, under the function, we are iterating over the array to swap rearranging the array around the pivot element.
Therefore, from the above results, we can conclude that the best-case time complexity for the quick sort algorithm is O(nlogn).
Worst Case:
The Worst-case occurs when either of the two partitions is unbalanced. This generally happens when the greatest or smallest element is selected as the pivot.
In this case, the pivot lies at the extreme of the array, and one subarray is always empty while the other contains n – 1 elements.
This way, in the first call, the array is divided into two subarrays of 0 & n – 1 elements respectively. For the second call, the array with n – 1 elements is divided into two subarrays of 0 & n – 2 elements respectively. This continues till only one element is left.
The time complexity, in this case, would be the sum of all the complexities at each step.
T(quicksort) = T(n) + T(n – 1) + T(n – 2) + …….. + 2 + 1
T(quicksort) = O((n * (n – 1))/2)
T(quicksort) = &O(n ^ 2)&
The following is the tree representation of this condition –
2. Quick Sort Space Complexity
In quick sort, the time complexity is calculated on the basis of space used by the recursion stack. In the worst case, the space complexity is O(n) because in the worst case, n recursive calls are made. And, the average space complexity of a quick sort algorithm is equal to O(logn).
From sorting to searching, Java DSA is essential. Join our free Java DSA course and become a proficient programmer in these core concepts.
Conclusion
- Quick Sort method sorts the elements using the Divide and Conquer approach.
- It has an average O(nLogn) complexity.
- It can be implemented in both recursive and iterative ways.
- Quick Sort is in-place, cache-friendly, and also a tail-recursive algorithm
Takeaways
Quicksort partitions an array and then calls itself recursively twice to sort the two resulting subarrays.
Complexity of Quick sort
- Time complexity – O(nlog(n))
- Space complexity – O(n)
FAQs
Q: Where is Quick Sort Used?
A: Quick sort is used in separating the Nth smallest or the largest element from an array. Being a fast sorting algorithm, quick sort is used by various departments in information retrieval. It is used for numerical computing where the efficient algorithms use priority queues and in turn quick sort for achieving accuracy. It is used where fast searching and/or sorting is the priority.
Q: Is Quick Sort a Stable Algorithm?
A: An algorithm is called stable if the relative order of two equal elements is preserved. Therefore, quick sort is not a stable algorithm because ordering is done on the basis of the pivot’s position.
Q: Why Quick Sort Runs Faster Than Merge Sort?
A: Quick sort is an in-place algorithm. But in merge sort, a new temporary array is required to merge the sorted subarrays. Therefore, quick sort is faster than merge sort.
Moreover, in quick sort, the worst case can be avoided by randomly choosing an element as the pivot, and performing sorting around it. Thus, a properly implemented quick sort has a time complexity of O(nlogn) in the average case.
Q: Why Quick Sort is Preferred for Array?
A: Quick sort is cache-friendly, which means it does not create unnecessary buffers in the cache memory and slows the system down. It is because, when used for arrays, quick sort has a good locality of reference
