Quicksort Algorithm Explained [With Example]

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:

1. Elements less than the pivot element
2. Pivot element
3. Elements greater than the pivot element

Pivot element can be chosen from the given numbers in many different ways:

1. Choosing the first element
2. Choosing the last element (example shown)
3. Choosing any random element
4. Choosing the median

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

How does it work?

These are the steps followed in the quick sort algorithm:

1. We choose our pivot as the last element, and we start to partition (or divide) the array for the first time.
2. In this partitioning algorithm, the array is broken into 2 subarrays such that all the elements smaller than the pivot will be on the left side of the pivot and all the elements greater than the pivot will be on the right side of it.
3. And the pivot element will be at its final sorted position.
4. The elements in the left and right subarrays do not have to be sorted.
5. Then we recursively pick the left and right subarrays, and we perform partitioning on each of them by choosing a pivot in the subarrays and the steps are repeated for the same.

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

Complexity Analysis

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) 

Conclusion

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.