Introduction to QuickSort Algorithm in C++
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++.
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?
- Working of the QuickSort Algorithm
- QuickSort Implementation in C++
- Time Complexity Analysis of QuickSort
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:
Best-suited Data Structures and Algorithms courses for you
Learn Data Structures and Algorithms with these high-rated online courses
Working of the QuickSort Algorithm
The key function used in QuickSort is 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:
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.
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:
- 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.
- 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.
- Now that our first index is set, we set the pointer to the second index element and repeat the process.
- 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.
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.
The final sorted array looks like this:
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 elementsvoid swap(int* a, int* b){ int temp = *a; *a = *b; *b = temp;}
//Function that takes the last element as pivotint 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 QuickSortvoid 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 arrayvoid Array(int arr[], int size){ int i; for (i = 0; i < size; i++) cout << arr[i] << " "; cout << endl;}
//Driver Codeint 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;}
Output:
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 pivotint 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 QuickSortvoid 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 arrayvoid Array(int arr[], int size){ for (int i = 0; i < size; i++) { cout << arr[i] << " "; } cout << endl;}
//Driver Codeint 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;}
Output:
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.
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
Top Picks & New Arrivals
