Quick Sort is a very popular sorting algorithm also known as partition exchange sort. Quick sort follows divide-and-conquer strategy to sort an array elements. In this algorithm first we select the pivot element. This pivot element can be selected either the left most element or right most element.
After selecting pivot element, first divide an unsorted array into two smaller sub-arrays on the basic of pivot element and then further sub-array if possible. Elements of the Left sub arrays will be lesser than pivot element and the element in the right subarray will be greater than pivot element.
Quick Sort algorithm was developed by C. A. R. Hoare which is a widely used sorting algorithm to sort the elements of a list. In the average case, Quick Sort makes O(n log n) comparisons to sort an array of n elements. And in the worst case, it has a quadratic running time O(n2).
- Quick sort is a recursive algorithm that follows a divide-and-conquer strategy.
- The time complexity of the Quick Sort algorithm is O(nlogn) in the average case.
- The time complexity of the Quick Sort algorithm is O(n2) in the worst case.
- Quick Sort is an in-place sorting algorithm it means it takes an only a constant amount of memory to perform the sorting algorithm.
- Quick Sort is often the efficient sorting algorithm that is used by most of the language libraries to perform sorting.
So in this lesson we will see working of Quick Sort algorithm with an example.
Here the Steps of how quick sort algo works
Here are the steps of the quick sort algorithm
- First Choose a Pivot element from the Array. Pivot element will be either the first element or last element of the array.
- After selecting Pivot element we have to Partition the array into two sub-arrays. One sub-array will contain the elements less than the pivot, and another sub array will contain the elements greater than the pivot.
- To do this, you have to maintain two pointers. One Pointer will be at the start and another pointer will be at the end of the array. Move the start pointer towards the end of the array until you find an element greater than the pivot. Similarly, move the end pointer towards the start of the array until you find an element less than the pivot. Swap these two elements and continue until the start pointer is greater than or equal to the end pointer.
- Recursively sort the two sub-arrays created. This can be done by calling the quick sort function on each sub-array.
- Concatenate the sorted sub-arrays and return the resulting array.
Detailed explanation of quick sort with example
Lets take an array arr = [10,5,12,8,2,11,17] that need to be sorted using quick sort.
[10,5,12,8,2,11,17]Step 1: First we will choose a pivot element. Pivot element can be either first one or the last one.
Here we are choosing the first element of the array as the pivot, which is 10.
Step 2: Partition the array
After selecting the pivot array, we will partition the array into two sub-array. One sub array will contain elements less than or equal to the pivot, and another sub array will contain elements greater than the pivot. To do this, we are taking two pointers i and j.
[10,5,12,8,2,11,17]
↑ i jAs
Pivot = 10, i = 0, arr[i] = 5, j=6 and arr[j] = 17
Now i will move towards right and j will move towards left and will match the value at i index with pivot and value of j index with pivot. If the element at i index is smaller than pivot value then i will increase by 1 and move towards right. Similarly if element at j will be greater than pivot element then j will be increase by 1 and will move towards left.
Now we have to keep in mind, when the element at i index is greater than pivot then we have to stop there. Similarly if the element at j index is smaller than pivot then we have to stop.
Lets back to our example
Pivot = 10, Value at arr[i] = 5, i=1 which is smaller than pivot, will increase i by one and move right.
[10,5,12,8,2,11,17]
↑ i jPivot = 10, Value at arr[i] = 12, i=2 which is greater than pivot, will stop here. Here we compare arr[j] = 17, j=6 with pivot, pivot is smaller then decrement in j by 1. so now j is 5.
[10,5,12,8,2,11,17]
↑ i jAgain arr[j] = 11 (j=5), greater then pivot, decrease j by 1.
[10,5,12,8,2,11,17]
↑ i jAgain arr[j] = 2 (j=4), Here 2 is smaller than pivot. So we will perform swapping between arr[i] and arr[j]. Pivot will be at the same place. So after swapping array will look like
[10,5,2,8,12,11,17]
↑ i jAgain i will move towards right and stop at 12 because 12 is greater than pivot element.
And j will start moving towards left and stop at 8 because 8 is smaller than Pivot element. And also i become greater than j.
[10,5,2,8,12,11,17]
↑ j iHere swapping will be done between pivot and arr[j]=8. So after swapping array will look like
[8,5,2,10,12,11,17]Here you can see in first pass all the element in left of pivot is smaller than pivot. And all the element right of pivot is greater than pivot.
Here array will broken into two sub array.
sub-array 1 will be [8,5,2] and Sub array 2 will be [12,11,17]
Again same process will apply on the above two sub array.
Once array is broken in sub array, then conquer will be happen to form sorted array again.
Algorithm of quick sort
Quick Sort Pivot Algorithm
Step 1 – Initialize an array arr
Step 2 − Choose the First element as a pivot element
Step 3 − Take two pointers l and r. Where l is pointing to left most element excluding pivot and r is pointing to the right most element.
Step 4 − Move the left pointer l towards right until it reached at the element that is greater than or equal to the pivot element. If l pointer reached at that element stop there.
Step 5 − Move the right pointer r to the left until it points to an element that is lesser than or equal to the pivot element. If this condition matched just stop there.
Step 6 − Now swap the left pointer element with the right pointer element.
Step 7 − Repeat the above step(4-6) util left pointer become greater than right pointer.
Step 8 – If left pointer become greater than right pointer, now swap the pivot element with right pointer element.
Step 9 – Here Pivot element is now at sorted position.
Time complexity of Quick Sort
Best-case performance: O(nlogn)
Average performance: О(nlogn)
Worst-case performance: О(n2)
Space Complexity: O(1)
Pseudo Code of Quick Sort
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high); // Get the pivot index
quick_sort(arr, low, pivot - 1); // Sort the left partition
quick_sort(arr, pivot + 1, high); // Sort the right partition
}
}
int partition(int arr[], int low, int high) {
int pivot = arr[low]; // Choose the first element as the pivot
int left = low + 1;
int right = high;
while (1) {
// Move left pointer to the right until we find an element that is greater than or equal to the pivot
while (left <= right && arr[left] < pivot) {
left++;
}
// Move right pointer to the left until we find an element that is less than or equal to the pivot
while (left <= right && arr[right] > pivot) {
right--;
}
if (left <= right) {
// Swap the elements at left and right pointers
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
} else {
// Swap the pivot with the element at right pointer
int temp = arr[low];
arr[low] = arr[right];
arr[right] = temp;
return right; // Return the pivot index
}
}
}Quick Sort Program in C
#include <stdio.h>
void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}
int partition(int arr[], int l, int r) {
int pivot = arr[l];
int i = l + 1;
int j = r;
while (1) {
while (i <= j && arr[i] <= pivot) {
i++;
}
while (i <= j && arr[j] > pivot) {
j--;
}
if (i <= j) {
swap(&arr[i], &arr[j]);
} else {
break;
}
}
swap(&arr[l], &arr[j]);
return j;
}
void quicksort(int arr[], int l, int r) {
if (l < r) {
int pi = partition(arr, l, r);
quicksort(arr, l, pi - 1);
quicksort(arr, pi + 1, r);
}
}
int main() {
int arr[100],i,j,n,key;
printf("Enter the number of elements you want to sort:\n");
scanf("%d",&n);
printf("Now enter the %d elements you want to sort: \n",n);
for(i=0;i<n;i++){
scanf("%d",&arr[i]);
}
printf("before sorting:\n");
for(i=0;i<n;i++){
printf("%d \t",arr[i]);
}
quicksort(arr, 0, n - 1);
printf("\nSorted array: \n");
for (int i = 0; i < n; i++) {
printf("%d \t", arr[i]);
}
return 0;
}Output:
Enter the number of elements you want to sort:
6
Now enter the 6 elements you want to sort:
23
11
12
78
99
1
before sorting:
23 11 12 78 99 1
Sorted array:
1 11 12 23 78 99