Quick Sort

We have already discussed the Bubble Sort Algorithm and Merge Sort Algorithm, and in this post, we are going to discuss ALGORITHM OF QUICK SORT.

Quick Sort Algorithm is also a divide and conquer Algorithm, but it is considered to be better than Merge Sort Algorithm in practical cases. 

Why Quick Sort is better than Merge Sort Algorithm..??

The reason behind it is that there is always a scope of improvement in quick Sort.

Quick Sort works by selecting a ‘pivot’ element from the dataset and partitioning the other elements into two sub-dataset, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. 

In Quick Sort, you always have the freedom to choose pivot element and you can always choose it according to the datasets.

We have already discussed the Divide and Conquer approach in Merge Sort Algorithm. Please go through it.

What is a pivot element?

The pivot element is the boss of all the elements. All other elements are arranged according to the pivot element.

Let’s take an example,

algorithm of quick sort

Let’s consider the first element as a pivot element and we want to arrange the other elements accordingly.

We will arrange other elements such that all elements smaller than pivot will come to the left side of the pivot and all elements greater than pivot will come to the right side of the pivot.

algorithm of quick sort

Now as you can see we have arranged the elements according to our pivot element.

NOTE that the above array is not a sorted array, the elements on the left side of the pivot element are smaller than it, and elements on the right side are greater. That’s it.

This is the use of the pivot element in the Quicksort Algorithm. You always have the right to choose a pivot element. Some other ways of selecting pivot element are – 

(i) It can be the first element of the array. (As discussed above)
(ii) It can be the last element of the array.
(iii) It can be the middle element of the array.
(iv) It can be chosen randomly. (Randomised Quick Sort)

Now the question arises, How to arrange elements according to pivot elements?

The implementation is very much simple, let us consider that we choose the first element as the pivot element.

Let’s see the code first,

int find_pivot(int arr[], int low, int high)
{
    int pivot = arr[low];
    
    int p_index = low+1;
    for(int i = low+1; i <= high; i++)
    {
        if(arr[i] <= pivot) 
        {
            swap(arr[i], arr[p_index]);
            p_index++;
        }
    }
    swap(arr[p_index-1], arr[low]);
    return p_index-1;
}

Let us consider the same example to understand the code,

algorithm of quick sort

(i) For this example, low = 0 & high = 6. Also pivot element is the first element of the array.

Now we use a pointer variable to keep track (p_index). Initially p_index = 1.

(ii) Now we will run a loop and we will check whether any element in the array is smaller than it, if we find such an element we will swap it with the element present at p_index and then we increment the p_index.

(iii) We will follow these steps until we iterate through the array. Lastly, we will swap the elements of (p_index – 1) and the pivot element.

Let us visualize it what we have discussed above,

algorithm of quick sort
algorithm of quick sort

The arrow indicates the p_index. Initially p_index = low + 1.

Since 1 < 4, we swap arr[i] and arr[p_index], in this case, both are same so no swapping takes place, and then we increment p_index.

Again in 4th step, since 3 < 4, we swap arr[i] (3) and arr[p_index] (7) and then again we increment the p_index.

We follow these steps till we iterate all the elements of the array, at last, we swap arr[p_index-1] and pivot element so that element lesser than pivot element comes to its left side and element greater than it comes to the right side.

I hope this explanation and pictorial diagram make your concept clear.

Partition Algorithm


As we know Quick Sort is a divide and conquer algorithm, here also we have to divide the datasets into individual datasets as we did in Merge Sort Algorithm.

But here we will not divide the datasets into two equal halves instead we will divide it according to pivot element.

The approach is very simple, we will find p_index from the above algorithm and then we will divide the datasets into two halves accordingly.

Let’s see the code for clarification,

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int p_index = find_pivot(arr, low, high);

        quickSort(arr, low, p_index - 1);
        quickSort(arr, p_index + 1, high);
    }
}

This algorithm looks similar to the merge Sort first_step algorithm. Yes, both algorithms are similar because both algorithms divide the dataset into two halves.

But there is a difference, in merge sort we were dividing the array into two equal halves but here we are dividing it w.r.t pivot element.

Another difference is that here we are not merging datasets as we are doing in the case of merge sort.

Quick sort is an in-place Algorithm which means this Algorithm doesn’t require any extra space.

Let us understand this Algorithm by taking an example,

algorithm of quick sort

Now we will update this array according to pivot element, here pivot element is 6.

algorithm of quick sort

This is how recursion takes place, initially we find the pivot element of the original array and update the array accordingly.

Then we call recursion to the left part as well as the right part of the pivot index, we again find the pivot element for that sub-array and accordingly we move on.

At last, we finally get a sorted array. I hope Quick Sort is clear to you.

Analysis of Quick Sort Algorithm


Quick Sort Algorithm depends on the pivot element and it also involves the process of partitioning, so for an unsorted array, the average time complexity is O(n log(n)).

Best Case Time Complexity: O(n*log n)
Average Case Time Complexity: O(n*log n)
Worst Case Time Complexity: O(n^2)


Worst case of Quick Sort is O(n^2)

Let us consider this above array,

The given array is already sorted in ascending order and we want to apply quick Sort in this above array.

I know you might be thinking that why we are sorting this array since it is already sorted?

Sometimes, in real-world problem datasets are not in your control. So there is a chance you can get a sorted array.

So it’s better we should design Algorithms considering worst cases.

Now for the above array, pivot will be 1. But after partitioning, left subarray will be empty and right subarray will have remaining (n-1) elements.

Again for the right subarray, pivot will be its leftmost element, and again its left subarray will be empty and right subarray will have (n-2) elements.

This process will go on and thus time complexity would be –

T(n) = n + (n-1) + (n-2) + … + 3 + 2 + 1
= ((n) * (n+1) / 2)
= O(n^2)

Hence worst case has O(n^2) time complexity.

However worst case Complexity can be solved by selecting a suitable pivot element. This is the advantage that Quick Sort gives us, we can always avoid worst-case time complexity by picking up the appropriate pivot element.

Complete Quick Sort in C/C++

#include<bits/stdc++.h>
using namespace std;

int find_pivot(int arr[], int low, int high)
{
    int pivot = arr[low];
    
    int p_index = low+1;
    for(int i = low+1; i <= high; i++)
    {
        if(arr[i] <= pivot) 
        {
            swap(arr[i], arr[p_index]);
            p_index++;
        }
    }
    swap(arr[p_index-1], arr[low]);
    return p_index-1;
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int p_index = find_pivot(arr, low, high);

        quickSort(arr, low, p_index - 1);
        quickSort(arr, p_index + 1, high);
    }
}

int main()
{
	int n;
	scanf("%d",&n);

	int arr[n];
	
	for(int i=0;i<n;i++) {
		scanf("%d",&arr[i]);
	}
	
        quickSort(arr,0,n-1);
	
        for(int i=0;i<n;i++){
		printf("%d ",arr[i]);
	}
	printf("\n");
	return 0;
}

Randomized Quick Sort Algorithm

As we have observed that choosing a specific pivot element may take O(n^2) time complexity for some cases.

Randomized Quick Sort is the best solution for avoiding such cases.

Randomized Quick Sort generates a random pivot element which reduces the possibility of O(n^2) time complexity to almost 0%.

How to generate random numbers ..?

For this we will use random generator function, Let’s see its code.

int main()
{
	srand(time(NULL));
	printf("%d\n", rand()%100);

	return 0;
}

Here, the rand() function is used to generate random numbers and srand() function sets the starting point for producing a series of pseudo-random integers.

We use time(NULL) as seed value because time varies every millisecond which increases our probability of generating different random numbers.

The above code will generate random numbers in the range [0, 99].

Now we will use this random generator to generate random pivot indexes.

Let’s see the code of randomized Quicksort in C/C++,

#include<bits/stdc++.h>
using namespace std;

int random_index(int low, int high)
{
    srand(time(NULL));
    int index = low + (rand() % (high - low + 1));
    
    return index;
}

int find_pivot(int arr[], int low, int high)
{
    int index = random_index(low, high);
    
    swap(arr[index], arr[low]);
    
    int pivot = arr[low];
    
    int p_index = low+1;
    for(int i = low+1; i <= high; i++)
    {
        if(arr[i] <= pivot) 
        {
            swap(arr[i], arr[p_index]);
            p_index++;
        }
    }
    swap(arr[p_index-1], arr[low]);
    return p_index-1;
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int p_index = find_pivot(arr, low, high);

        quickSort(arr, low, p_index - 1);
        quickSort(arr, p_index + 1, high);
    }
}

int main()
{
    int n;
    scanf("%d",&n);

    int arr[n];
    
    for(int i=0;i<n;i++) {
        scanf("%d",&arr[i]);
    }
    
        quickSort(arr,0,n-1);
    
        for(int i=0;i<n;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
    return 0;
}

Here we are generating random index in the range (low, high) and we are swapping that index with arr[low], so in general, we are always generating random arr[low].

In this way, we can get rid of quadratic worst-case time complexity. For randomized Quick Sort worst-case complexity changes to O(n*log n).

I hope both Quick Sort and Randomised Quick Sort is clear to you all.

That’s all folks…!!!

Abhishek is currently pursuing CSE from Heritage Institute of Technology, Kolkata. He has a great interest in Data Structures and Algorithms, C++, Language, Competitive Coding, Android Development. His hobbies are Learning new skills, Content Writing, Competitive Coding, Teaching contents to Beginners.

Leave a Comment

Your email address will not be published. Required fields are marked *