Coders Packet

Performing Quick Sort Using Randomized Pivot in C++

By John Jayakumar H

Hello friends, today we'll bring down worst-case time complexities of quicksort, by combining randomization along with quicksort in C++.

Here's the  C++ code

#include
#include
using namespace std;

void swap(int *a, int *b)
{
  int temp; 
  temp = *a;
  *a = *b;
  *b = temp;
}

int partition(int a[], int small, int big)
{
  int pivot, p, i;
  p = small;
  pivot = big;
 
  for(i=small; i < big; i++)
  {
    if(a[i] < a[pivot])
    {
      swap(&a[i], &a[p]);
      p++;
    }
  }
  swap(&a[pivot], &a[p]);
 
  return p;
}
int pivotrandom(int a[], int small, int big)
{
  int pvt, n, temp;
  n = rand();
  pvt = small + n %(big-small+1);
 
  swap(&a[big], &a[pvt]);
 
  return partition(a, small, big);
}
 
int qsort(int a[], int small, int big)
{
  int pvtindex;
  if(small < big)
  {
    pvtindex = pivotrandom(a, small, big);
    qsort(a,small,pvtindex-1);
    qsort(a, pvtindex+1, big);
  }
  return 0;
}
 
int main()
{
  int n, i;
  cout<<"\nEnter the List of Numbers To be Sorted: ";
  cin>>n;
 
  int arr[n];
  for(i = 0; i < n; i++)
  {
    cout<<"Enter Element No "<<i+1<<": ";
    cin>>arr[i];
  }
 
  qsort(arr, 0, n-1);
  cout<<"\nSorted Order is";
  for (i = 0; i < n; i++)
        	cout<<", "<<arr[i];
 
  return 0;
}

The Output will be

                 

UNDERSTANDING THE ALGORITHM

Quicksort is a very powerful algorithm for sorting. It divides the array into smaller sub-arrays and then sorts these sub-arrays. In this code, we use the header file. This header file has a lot of mathematical functions. The first function created is swap which exchanges values between two variables. Here we use pointers to exchange their addresses. The partition function is used to split the array into sub-arrays. i is used in the iteration of elements in the array. pvtindex is used to mark the final position of the pivot. At last, it interchanges values of big and pvt. The pivotrandom function is for the random selection of the pivot. By randomly selecting the pivot we boost the average time complexity of quicksort to O(N log N). Then we execute the sorting algorithm. After selecting randomly an element as pivot, using the pivotrandom function, we divide the array. In quicksort, partitioning is the means by which we break down the given array into two or more subarrays. The array elements are then put in respective places where elements smaller to the pivot are moved to the left side and the elements greater to the pivot are moved to the right side of the pivot. The pivot will be positioned in its sorted position. The elements at the left side and right side of the pivot may not be in sorted order. So after that, it sorts the subarrays, in which the elements which are on the left side of the pivot and the elements on the right side of the pivot are sorted by subdividing the array by picking a pivot in the subarrays and sorts it.

                                            

Download project

Reviews Report

Submitted by John Jayakumar H (JohnJayakumar)

Download packets of source code on Coders Packet