QuickSort Using Random Pivoting in C++

This tutorial will discuss how to use quicksort using the random pivots in C++.

We know that quicksort is based on the divide and conquer approach. It is different from the Merge sort because it does not require extra space for merging two sorted lists.

In normal quicksort without using randomization, we manually select the pivot like first element, last element, or median element.

Algorithm or Procedure:

First, from the given subpart of the array randomly pick the pivot element.

Now we need to partition the element around the pivot such that smaller elements should come to the left of the pivot and larger elements to the right of the pivot.

We need to consider these left and right subparts as new sub-array.

Repeat the same procedure until the array is leftover with a single element.

Pseudocode:

rearrange_partition(list[], start, end) 
    pivot = list[end]
    i = start   
    for j := start to end – 1 do
        if list[j] <= pivot then
            swap list[i] with list[j]
            i = i + 1
    swap list[i] with list[end]
    return i

random_partition(list[], start, end)
    r = Random Number between start to end
    Swap list[r] and list[end]
    return partition(list, start, end)

randomquicksort(list[], start, end)
    if start < end
        rp = random_partition(list, start, end)
        quicksort(list, start , rp-1)
        quicksort(list, rp+1, end)

 

Follow the comments in the code for better understanding.

C++ Code: QuickSort Using Random Pivoting

#include <bits/stdc++.h>
using namespace std;

//function that rearranges the array based on the pivot
int rearrange_partition(int list[], int start, int end)
{
    int pivot_ele = list[end];//pivot element
   
    int i = (start - 1);//smaller element's position
 
    for (int j = start; j <= end - 1; j++)
    {   //check if the array element currently is smaller than or equal to this pivot
        if (list[j] <= pivot_ele) {
            //if so then increase the position of smaller element
            i++;
            swap(list[i], list[j]);
        }
    }

    swap(list[i + 1], list[end]);
    return (i + 1);
}


//function to choose pivot randomly
int random_partition(int arr[], int low, int high)
{
    //this generates a random number between low and high 
    srand(time(NULL));
    int random_index = low + rand() % (high - low);
    
    //swap both the elements at random_index and the last element
    swap(arr[random_index], arr[high]);
 
    return rearrange_partition(arr, low, high);
}


//function showing recursive implementation of quicksort
void randomquicksort(int list[],int start,int end){
    if(start < end) {
        int partition_index = random_partition(list, start, end);
        randomquicksort(list, start, partition_index - 1);
        randomquicksort(list, partition_index + 1, end);
    }
 }


int main(){  
int size;
cout<<"Enter the size of the array: ";
cin>>size;
int list[size];
cout<<"Enter the elements of the array: "<<endl;
for(int i=0;i<size;i++){
   cin>>list[i];
}

randomquicksort(list,0,size-1);
//after sorting
cout<<"The array elements after sorting are: "<<endl;
for(int i=0;i<size;i++){
    cout<<list[i]<<" ";
}
  
    return 0;
}

 

Input:

Enter the size of  the array: 10
Enter the elements of the array:
8 7 5 6 9 2 4 1 3 4

Output:

The array elements after sorting are:
1 2 3 4 4 5 6 7 8 9

Time Complexity:

Average and Best case Time Complexity: O(n*log(n))

Worst Case Complexity: O(n^2)

But by using randomization we can reduce the worst-case time complexity.

Space Complexity:

We are not using any extra space for implementing this algorithm.

Also read: Generate a random element in C++ from an array

Leave a Reply

Your email address will not be published.