Are you looking for Implementation of QuickSort in C++? In this article, I will go through the QuickSort implementation in C++ and provide you detailed knowledge about the algorithm of this sorting type.
QuickSort, like Merge Sort, is a Divide and Conquer algorithm. It selects a pivot element and partitions the specified array around that pivot. QuickSort comes in a variety of flavors, each of which selects pivot in a unique or different way.
Different Ways Pivot are selected in QuickSort
Let us see what are the different ways Pivot is usually selected in QuickSort.
- First element is always picked as Pivot.
- Last element is always picked as Pivot.
- Select any randome element as Pivot.
- Select Median as the Pivot.
Hence QuickSort can be performed by selecting the pivot as any one of the ways mentioned above. Hence here the process of selecting the pivot is to put it in the correct place once iteration is completed.
Partitioning is the most important operation in quickSort(). Given an array and a pivot element x, the goal of partitioning is to place x in the correct position in the sorted array, with all smaller elements (less than x) placed before x and all larger elements (greater than x) placed after x. All of this should be completed in a linear manner.
Psuedo Code for QuickSort (Recursion)
Let us see the Psuedo Code for QuickSort algorithm and understand how it would work in the programming environment.
/* low --> Starting index, high --> Ending index */
quickSort(giveArr[], low, high)
{
if (low < high)
{
/* pivot is partitioning index, giveArr[p] is now
at right place */
pivot = partition(givenArr, low, high);
quickSort(arr, low, pi - 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}QuickSort in C++ Implementation Recursion
Let us see the recursive implementation of QuickSort in the below example code. Note that this is the implementation of the above pseudo-code where we are taking the last element as pivot.
#include <iostream>
#include <algorithm> // std::swap
#include <vector> // std::vector
/* This function uses the last element as the pivot,
inserts it in the correct position in the sorted array,
and moves all smaller (smaller than pivot) elements to the
left of pivot and all larger elements to the right of pivot. */
int getPartition (std::vector<int> &givenArray, int low, int high)
{
int pivot = givenArray[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (givenArray[j] <= pivot)
{
i++; // increment index of smaller element
std::swap(givenArray[i], givenArray[j]);
}
}
std::swap(givenArray[i + 1], givenArray[high]);
return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(std::vector<int> &givenArray, int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = getPartition(givenArray, low, high);
// Separately sort elements before
// partition and after partition
quickSort(givenArray, low, pi - 1);
quickSort(givenArray, pi + 1, high);
}
}
// Driver program to test the QuickSort Function
int main()
{
std::vector<int> givenArray{5,2,7,1,8,4,6,10,9,3};
int n = givenArray.size();
quickSort(givenArray, 0, n-1);
std::cout<<"Sorted array: \n";
for(int x:givenArray)
std::cout<<x<<" ";
return 0;
}
Time and Space Complexity of QuickSort
Worst case: Worst case in QuickSort Sorting Algorithm occurs mostly when we select the lowest or highest element in the array as a pivot. For example, when all the elements are in descending order, in that case, any pivot select will be sorting only itself leading to run the code for n2 time.
Time Complexity: O(n2)
To fix this issue we can use Randomized Quick Sort to get the average time complexity as mentioned below.
Average Case: When you can unsorted array, not in descending order then quickSort runs in average time complexity that is similar to Merge Sort Algorithm.
Time Complexity: O(nlogn)
Wrap Up
If you liked the answer for QuickSort in C++ then please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.
Further Read:
