Introduction to QuickSort Algorithm in C++

Introduction to QuickSort Algorithm in C++

5 mins read4.7K Views Comment
Updated on Jan 16, 2023 12:05 IST

In this tutorial, we are going to learn about a common sorting technique – QuickSort, and we are going to see how this technique is implemented in C++.

2022_07_Add-a-subheading-1.jpg

In today’s article, we will be covering the quicksort algorithm in C++ in detail. But, before moving further, let’s go over the sections that we will be covering: 

What is QuickSort? 

The QuickSort algorithm is based on the strategy of divide-and-conquer where an array is split into sub-arrays around a selected pivot element from the array. 

The pivot element should be positioned so that elements less than the pivot are on its left, and elements greater than the pivot, are on its right. The resulting sub-arrays are further divided using the same approach and this process continues until each sub-array contains a single element. 

At this point, we have the sorted elements at hand, which are then combined into a sorted array.  

There can be variations in the QuickSort algorithm where the pivot element can be selected in different ways, such as: 

  • Select the first element as the pivot (implemented in C++ below) 
  • Choose the last element as the pivot (implemented in C++ below) 
  • Select a random element as the pivot 
  • Select the median as the pivot 

Now, let’s understand the logic behind this algorithm in detail: 

Working of the QuickSort Algorithm 

The key function used in QuickSortis the partition(). This method places the pivot element x? at its correct position as it would be in a sorted array, and places all smaller elements before x?, and all greater elements after x?.  

Let’s understand through an example. Suppose we need to sort the following array: 

2022_07_image-82.jpg

Step 1: Select the pivot element 

  • There can be variations in the QuickSort algorithm where the pivot element can be selected from different positions. In this case, we will be selecting the right-most element of the array as our pivot
2022_07_image-83.jpg

Step 2: Rearrange the array 

  • Now that we have selected the pivot, we will rearrange the array so that the elements smaller than the pivot are placed on its left, and the elements greater than the pivot are placed on its right.  Let’s see how this is done: 
2022_07_image-85.jpg
  • We fix a pointer at the pivot element. We then compare the pivot with the elements beginning from the first index, as shown above.
  • If the element being compared is greater than the pivot, we set a second pointer to that element. 
2022_07_image-86.jpg
  • Now, the pivot is compared to the other elements.  
  • If we reach an element that is smaller than the pivot, we swap the smaller element with the greater element we had found earlier. 
2022_07_image-87.jpg
  • Now that our first index is set, we set the pointer to the second index element and repeat the process. 
2022_07_image-88.jpg
  • Again, we repeat the process with the pointer set to the third index element. This goes on till the last element is reached. Then, the pivot is swapped with the pointer.  
2022_07_image-89.jpg

Step 3: Divide the arrays 

  • The elements at the left of the pivot form a sub-array and elements to the right of the pivot form another sub-array. 
  • Pivot elements are chosen for each sub-array and steps 2 and 3 are repeated until each sub-array consists of a single element.  
  • At this point, you will notice that the array is already sorted. 
2022_07_image-91.jpg

The final sorted array looks like this: 

2022_07_image-93.jpg

Isn’t it simple to understand in an illustrated manner? 

QuickSort Implementation in C++

Now, let’s see how we implement QuickSort in C++ selecting the last element as a pivot: 

 
//QuickSort in C++
// Selecting last element as pivot
#include <bits/stdc++.h>
using namespace std;
//Function to swap two elements
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
//Function that takes the last element as pivot
int partition (int array[], int low, int high)
{
int pivot = array[high]; //Pivot
int i = (low - 1); //Index of smaller element and indicates the correct position of current pivot
for (int j = low; j <= high - 1; j++)
{
//If current element is smaller than the pivot
if (array[j] < pivot)
{
i++; //Increment index of smaller element
swap(&array[i], &array[j]);
}
}
swap(&array[i + 1], &array[high]);
return (i + 1);
}
//Main function that implements QuickSort
void QuickSort(int array[], int low, int high)
{
if (low < high)
{
//pi is partitioning index, arr[p] is now at the correct place
int pi = partition(array, low, high);
//Separately sort elements before and after partition
QuickSort(array, low, pi - 1);
QuickSort(array, pi + 1, high);
}
}
//Function to print an array
void Array(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
//Driver Code
int main()
{
int list[] = {11, 6, 9, 2, 14, 0};
int n = sizeof(list) / sizeof(list[0]);
QuickSort(list, 0, n - 1);
cout << "Sorted array: \n";
Array(list, n);
return 0;
}
Copy code

Output:

2022_07_image-97.jpg
Similarly, let’s see how to implement QuickSort by selecting the first element as a pivot:
 
//QuickSort in C++
// Selecting first element as pivot
#include <iostream>
#include <algorithm>
using namespace std;
//Function that takes first element as pivot
int partition(int arr[], int low, int high)
{
int i = low;
int j = high;
int pivot = arr[low];
while (i < j)
{
while (pivot >= arr[i])
i++;
while (pivot < arr[j])
j--;
if (i < j)
swap(arr[i], arr[j]);
}
swap(arr[low], arr[j]);
return j;
}
//Main function that implements QuickSort
void QuickSort(int arr[], int low, int high)
{
if (low < high)
{
int pivot = partition(arr, low, high);
QuickSort(arr, low, pivot - 1);
QuickSort(arr, pivot + 1, high);
}
}
//Function to print an array
void Array(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
//Driver Code
int main()
{
int arr[] = {6, 12, 8, 4, 20, 13, 9};
int size = sizeof(arr) / sizeof(int);
QuickSort(arr, 0, size - 1);
cout<<"Sorted array:"<<endl;
Array(arr, size);
return 0;
}
Copy code

Output:

2022_07_image-98.jpg

The QuickSort algorithm is used for: 

  • Commercial computing 
  • Numerical computing 
  • Information search 

This is the preferred sorting algorithm when time complexity matters. Let’s see why: 

Time Complexity Analysis of QuickSort 

The time taken by the QuickSort algorithm to sort a given array depends on the array itself along with the partition approach used. 

Suppose there are k? elements smaller than the pivot, and n? is the total number of elements (size of the array), then the general time taken by the algorithm can be expressed mathematically as shown below: 

T(n)=T(k)+T(n−k−1)+O(n) 

Where T(k)?? and T(n−k−1)??−?−? are the time taken by recursive calls. O(n)?? is the time taken by the partitioning call. 

The time complexities for various cases in QuickSort are as follows: 

Time Complexity
Best Case Time Complexity  O(n∗log n)?(?∗??? ?) 
Worst Case Time Complexity  O(n2)?(??) 
Average Time Complexity  O(n∗log n)?(?∗??? ?) 
Space Complexity  O(log n)?(??? ?) 

Best Case Complexity  
The best-case complexity occurs when the pivot element is the middle or nearest to the middle element of the given array. 

Worst Case Complexity  
The worst-case complexity occurs when the pivot element is either the greatest or the smallest element of the array. 

In such a scenario, the pivot element lies at either of the extreme ends of the sorted array. So, one sub-array will always be empty and the other will contain (n−1) elements. This, the QuickSort algorithm will be called only on the latter sub-array. 

Thus, the total number of comparisons: n∗(n−1) ~ n2 

Average Complexity  
The average complexity occurs when the pivot element of the array is neither in the middle nor at the extreme ends of the array.  

Space Complexity  
The space complexity is given as O(log n). 

Endnotes 

QuickSort is an in-place sorting technique that is widely used because of its quick and easy execution. In this tutorial, we focused on this algorithm in detail including its implementation in C++. Hope this article proved to be useful for you. We recommend you check out the following sorting algorithms as well.  

About the Author

This is a collection of insightful articles from domain experts in the fields of Cloud Computing, DevOps, AWS, Data Science, Machine Learning, AI, and Natural Language Processing. The range of topics caters to upski... Read Full Bio