QuickSort in C++ Implementation and Examples

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;
}
QuickSort in C++ Implementation and Examples

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)

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:

  1. Kruskal’s Algorithm Minimum Spanning Tree Complete Guide
  2. How to Find Diameter Of Binary Tree?
  3. Find First And Last Position of Element in Sorted Array
  4. N-ary Tree Level Order Traversal Solution Python C++
Share your love

One comment

Leave a Reply