Quicksort Algorithm Explained [With Example]
Updated on Dec 30, 2024 | 5 min read | 15.8k views
Share:
For working professionals
For fresh graduates
More
Updated on Dec 30, 2024 | 5 min read | 15.8k views
Share:
Quick Sort is based on the concept of Divide and Conquer algorithm, which is also the concept used in Merge Sort. The difference is, that in quick sort the most important or significant work is done while partitioning (or dividing) the array into subarrays, while in case of merge sort, all the major work happens during merging the subarrays. For quick sort, the combining step is insignificant.
Quick Sort is also called partition-exchange sort. This algorithm divides the given array of numbers into three main parts:
Pivot element can be chosen from the given numbers in many different ways:
For example: In the array {51, 36, 62, 13, 16, 7, 5, 24}, we take 24 as pivot (last element). So after the first pass, the list will be changed like this.
{5 7 16 13 24 62 36 51}
Enrol for the Machine Learning Course from the World’s top Universities. Earn Masters, Executive PGP, or Advanced Certificate Programs to fast-track your career.
Hence after the first pass, the array is sorted such that all elements less than the chosen pivot are on its left side and all greater elements on its right side. The pivot is finally at the position it is supposed to be in the sorted version of the array. Now the subarrays {5 7 16 13} and {62 36 51} are considered as two separate arrays, and same recursive logic will be applied on them, and we will keep doing this until the complete array is sorted.
Also Read: Heap Sort in Data Structure
These are the steps followed in the quick sort algorithm:
Shown below is how the algorithm works in C++ code, using an example array.
void QuickSort(int a[], int low, int high)
{
if(high<low)
return;
int p= partition(a,low,high);
QuickSort(a,low,p-1);
QuickSort(a,p+1,high);
}
int partition(int a[], int low, int high)
{
int pivot=a[high];
int i=low;
for(int j=low; j<high; j++)
{
if(a[j]<=pivot)
{
swap(&a[j],&a[i]);
i++;
}
}
swap(&a[i],&a[high]);
return i;
}
int main()
{
int arr[]={6,1,5,2,4,3};
QuickSort(arr,0,5);
cout<<”The sorted array is: “;
for(int i=0; i<6; i++)
cout<<arr[i]<<” “;
return 0;
}
Below is a pictorial representation of how quick sort will sort the given array.
Suppose the initial input array is:
So after our first partition, the pivot element is at its correct place in the sorted array, with all its smaller elements to the left and greater to the right.
Now QuickSort() will be called recursively for the subarrays {1,2} and {6,4,5} and continue till the array is sorted.
Must Read: Types of AI Algorithms You Should Know
Best Case Time Complexity: Ω(n*log n)
Average Time Complexity: Θ(n*log n)
Worst Case Time Complexity: O(n2)
If partitioning leads to nearly equal subarrays, then the running time is the best, with time complexity as O(n*log n).
Worst case happens for arrays with cases where the elements are already sorted, and pivot is chosen as the last element. Here the partitioning gives unbalanced subarrays, where all elements are already smaller than the pivot and hence on its left side, and no elements on the right side.
Space Complexity (considering recursion stack): O(n*log n)
Quicksort is a comparison-based algorithm and it is not stable. A small optimization that can be done, is to call the recursive QuickSort() function for the smaller subarray first and then the larger subarray.
Overall, Quick Sort is a highly efficient sorting technique that can give better performance than Merge Sort in the case of smaller arrays.
If you are keen on learning more, check out upGrad & IIIT-B’s PG Diploma in Machine Learning and AI Program.
Get Free Consultation
By submitting, I accept the T&C and
Privacy Policy
Top Resources