QuickSort Using Random Pivoting in C++
By RakeshThis 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.
Leave a Reply