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

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.

Submitted by John Jayakumar H (JohnJayakumar)

Download packets of source code on Coders Packet