Understanding Quicksort

Introduction

“Divide et impera.”

– Julius Caesar

These three powerful Latin words meaning “divide and conquer” were said more than two thousand years ago. Yet, the principle was so strong that it managed to rule our lives even now. But why?

The reason is that we humans love to simplify our work by dividing it into smaller parts. 

Keeping this fact in mind, people have developed computer algorithms that follow the divide and conquer principle. 

One of these algorithms is the quicksort algorithm used to sort the elements in an array. 

Now you may be wondering that you already know some other sorting technique, so what’s the use of knowing another?

Different algorithms have different time and space complexities. Thus, knowing quicksort is as vital as learning any other sorting algorithm. 

So, if you don’t know about quicksort already, just hang in there with me because together, we will learn all about quicksort in this article. 

Working of QuickSort

As we already know, quicksort is used to sort the elements of an array in ascending or descending order, but then how does it implement the divide and conquer principle?

In quicksort, an element is chosen as the pivot. Comparisons with it divide the array into two partitions, where the left side of the pivot has elements smaller than it while the right side has elements larger than it. 

Quicksort has then applied to both the partitions again, and the process is continued till the array is sorted. 

Now that we know how quicksort works, you are probably thinking, how do we choose the pivot?

There are four ways to choose the pivot:

1. Consider the first element as the pivot.
2. Consider the last element as the pivot.
3. Consider any random element as the pivot.
4. Use the Median of 3 methods. 

Let us now consider a quicksort example and understand the four different methods.

First element as the Pivot

After choosing a pivot, our next step is to swap the pivot with the last element and assign two counters for loops, i and j, as shown below:

We mentioned before that i and j are counters for loops, but for what loops?

In quicksort, we will keep on incrementing i till we find an element larger than the pivot, and we will keep on decrementing j till we find an element smaller than the pivot. 

When we find two such elements, we will swap them. 

To understand this, let us consider a quicksort illustration.

Here, i is not greater than the pivot, but j is less than the pivot, so we will increase i till our condition is met. 

Finally, i is greater than the pivot, so our next step would be to swap the elements in positions i and j. 

We will increment and decrement, i and j, respectively, till i > j.

Now that i has crossed j, we will swap the element in the i^th position and the pivot. 

Here, we can see that the elements to the left of the pivot are less than it, while the elements to the right of the pivot are greater than it. So we have got two partitions and the sorted position of the pivot (8).

Now, we will again apply the quicksort to the partitions. But, the right partition has only one element, so we’ll use a quicksort to the left partition only. 

Last Element as the Pivot

In the left partition, we can see that 0 is the smallest element, so it is already in its sorted position. Therefore, considering 0 as the pivot would be a waste of time, so let’s use the last element as the pivot here. We will also initialise the counters i and j. 

We already know how the counters are used in quicksort, but let’s see it once more for the sake of our understanding.

Here, again two partitions are formed where the elements to the left of the pivot are smaller than it, while the elements to the right are larger. 

Since we can see that the elements in the left partition are already sorted, we will ignore it. A computer program will, however, sort it again using quicksort.

Random Element as the Pivot

To sort the right partition we got, let us use the third method of considering the pivot. 

Instead of any random element, let us choose the element at the middle index as the pivot.

Here, the middle element is 3. So, we will consider that to be the pivot. 

Now that we have determined the pivot, we will continue the process as we have before.

Thus, the array is now like this.

The last three elements left can quickly be sorted by choosing the pivot following any of the methods mentioned above to give the sorted array as follows:

The Median of 3 Method

There is another method to choose the pivot element, the median of 3 methods. 

Previously, we had seen that we might encounter a situation where the element we’re choosing as a pivot is already in its sorted position. So, considering that element as the pivot would unnecessarily increase the complexity of the algorithm. 

To avoid this, the median of 3 methods is used to choose the pivot. 

Let us consider the same array as an example to understand how this method works. 

Here, the first element is 8, the last element is 0, and the median element (0+9/2 ≈ 4) is 6. 

In the median of 3 rule, we will first sort these three elements in ascending order and place them in the first, median and last positions, respectively, as follows:

As shown below, we will swap the element in the median position, i.e., 6, with the element in the second to the last position. The element in the second to the last position will now be our pivot. https://waterfordbanquet.com

Our next step is to assign the counters. i and j will be assigned a little differently from how we were doing it before, but why?

The reason is, we already sorted the first, last and the median (now the pivot) element before. So, the first and the last elements are already in the correct partition. 

Therefore i and j will be assigned as follows:

Therefore, the array is now as follows:

A new pivot is obtained for the left and the right partitions, and the process of quicksort continues to sort the entire array in ascending order. 

Algorithm of QuickSort

Now that we know how quicksort works, we can easily figure out its algorithm. 

Step 1: Choose the pivot following any of the four methods (the last element is commonly used as the pivot).
Step 2: Assign the counter i to the leftmost element’s index and the counter j to the rightmost element’s index, excluding the counter.
Step 3: If i is less than j, proceed.
Step 4: If the element in position i is less than the pivot, increment i.
Step 5: If the element in position j is greater than the pivot, decrement j.
Step 6: If the element in i is greater than the pivot and the element in position j is less than the pivot, swap the elements in i and j.
Step 7: If i is greater than j, swap the element in position i and the pivot.
Step 8: Continue the process for the left and the right partitions formed.

With this, we have completed the partition. 

Now, for the quicksort part,

Step 1: Declare a function with three parameters, an array (say arr) and two integer type variables (say i and j).
Step 2: If arr[i] < arr[j], partition the array between arr[i] and arr[j].
Step 3: Recursively call the function with three parameters, an array (arr) and two integers (i and (partition position - 1)).
Step 4: Recursively call the function with three parameters, an array (arr) and two integers ((partition position + 1), j).

Knowing the algorithm, we can easily use the syntax of different programming languages to write the code for quicksort in C, quicksort in Java or quicksort in Python.

Code for QuickSort in C++

The complete code for quicksort, considering the last element as the pivot (in C++), quicksort below:

#include<stdio.h>
int partition(int x[], int i, int j)
{
    int left=i, right=j-1, pivot=j, complete=0, t;
    while(!complete)
    {
    while(x[left]<=x[pivot] && pivot!=left)
  left++;
  if(pivot!=left)
  {
  t=x[pivot];
  x[pivot]=x[left];
  x[left]=t;
  pivot=left;
  }
  else
  complete=1;
  if(!complete)
  {
  while(x[right]>=x[pivot] && pivot!=right)
  right--;
  if(pivot!=right)
  {
  t=x[pivot];
  x[pivot]=x[right];
  x[right]=t;
  pivot=right;
  }
  else
  complete=1;
  }
    }
    return pivot;
}

void quicksort(int x[], int i, int j)
{
    int pivot;
    if(i<j)
    {
  pivot=partition(x, i, j);
  quicksort(x, i, pivot-1);
  quicksort(x, pivot+1, j);
    }
}

int main()
{
    int arr[] = {8,1,6,9,6,3,5,2,7,0};
    int len = sizeof(arr)/sizeof(arr[0]);
    quicksort(arr,0,len-1);
    for(int i=0;i<len;i++)
  cout<<arr[i];
    return 0;
}

Output:

0 1 2 3 5 6 6 7 8 9

QuickSort Time Complexity Analysis

Now that we know about quicksort, our next job would be to analyse the time complexity. 

To do that, let us again consider an array.

Best Case Complexity

Let us consider that each time, the partitioning occurs from the middle. We can visualise it like this:

Here, the number of iterations required to partition the array always sums up to n for each level.

To calculate the number of levels, we have to determine the number of times we divide the size of the initial array by two until we get 1. 

Therefore,

 n / 2^k = 1

=> n = 2^k

=> log₂(n) = log₂(2^k)

=> k = log₂(n)

Hence, the total time complexity will be a function of nlogn i.e. O(nlogn)

Now, most of the time, the partitioning is not precisely from the middle. This is the ideal case, and so it gives the best case complexity. 

Average Case Complexity

For average-case complexity, let us consider the partitioning to be in a 3:1 ratio.

The total number of iterations for partitioning in each level will again be n. 

For the number of levels, we have to determine the number of times we divide the size of the initial array by four till we get 1. 

Therefore,

 n / 4^k = 1

=> n = 4^k

=> log₄(n) = log₄(4^k)

=> k = log₄(n)

Hence the average case time complexity will again be O(nlogn).

Worst Case Complexity

In the worst-case scenario, we will be sorting an array that is already sorted. So, the partitioning diagram will be as follows:

Therefore, for large values of n, the time complexity will be, 

n + (n – 1) + (n – 2) + (n – 3) + … + 2 + 1 = n(n – 1) / 2 = (n² – n) / 2

Hence, the worst-case complexity is O(n²).

If you’ve come this far, don’t quit now. Try out QuickSort on CodeStudio and get it accepted right away.

Advantages of Merge Sort Over QuickSort

Like quicksort, merge sort is another divide and conquer algorithm following a similar method to sort arrays. 

Then why do we need two different algorithms?

To understand this, let us compare and contrast the two algorithms.

Property	QuickSort	Merge Sort
Partition of elements	Partitions are made in any ratio.	Partition is made into two halves.
Worst-case complexity	O(n2)	O(n.log n)
Suitability	It works well on small arrays.	It works well on any array, irrespective of the size.
Speed	Works comparatively faster for small data sets.	It has a consistent speed for all sizes of data sets.
Storage Requirements	Less	More
Efficiency	Inefficient for large data sets.	Comparatively more efficient.
Sorting Method	Internal	External
Stability	Not stable	Stable
Preferred Use	Arrays	Linked Lists

Therefore, we can conclude that merge sort is often more helpful than quicksort, especially for large data sets.

Frequently Asked Questions

Key Takeaways

In this article, we learned about quicksort, how it works and how to implement it, but this isn’t the end.

Keeping the theoretical knowledge at our fingertips helps us get about half the work done. To gain complete understanding, practice is a must. A variety of coding questions from interviews are available here.

Apart from this, you can also check CodeStudio, where you’ll find thousands of other coding questions to practice and interview experiences of scholars in renowned product-based companies.

Happy learning!