C++ Programming Code Examples C++ > Sorting Searching Code Examples Program to Implement Quick Sort with Given Complexity Constraint Program to Implement Quick Sort with Given Complexity Constraint - Quick sort is based on an algorithmic design pattern called divide-and-conquer. - The average time complexity is O(n*log(n)) but the worst case complexity is O(n^2). - To reduce the chances of the worst case we have implemented Quicksort using randomization. - Here we will be selecting the pivot randomly. - Randomly select pivot value from the given subpart of the array. - Partition that subpart so that the values left of the pivot are smaller and to the right are greater from the pivot. - Consider both as new sub-array and repeat step 1 until only one element left in subpart. - Display the result. - Exit. C++ program to implement Quick sort using randomization. #include<iostream> #include<cstdlib> using namespace std; // Swapping two values. void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } // Partitioning the array on the basis of values at high as pivot value. int Partition(int a[], int low, int high) { int pivot, index, i; index = low; pivot = high; // Getting index of pivot. for(i=low; i < high; i++) { if(a[i] < a[pivot]) { swap(&a[i], &a[index]); index++; } } // Swapping value at high and at the index obtained. swap(&a[pivot], &a[index]); return index; } // Random selection of pivot. int RandomPivotPartition(int a[], int low, int high) { int pvt, n, temp; n = rand(); // Randomizing the pivot value in the given subpart of array. pvt = low + n%(high-low+1); // Swapping pvt value from high, so pvt value will be taken as pivot while partitioning. swap(&a[high], &a[pvt]); return Partition(a, low, high); } // Implementing QuickSort algorithm. int QuickSort(int a[], int low, int high) { int pindex; if(low < high) { // Partitioning array using randomized pivot. pindex = RandomPivotPartition(a, low, high); // Recursively implementing QuickSort. QuickSort(a, low, pindex-1); QuickSort(a, pindex+1, high); } return 0; } int main() { int n, i; cout<<"\nEnter the number of data element to be sorted: "; cin>>n; int arr[n]; for(i = 0; i < n; i++) { cout<<"Enter element "<<i+1<<": "; cin>>arr[i]; } QuickSort(arr, 0, n-1); // Printing the sorted data. cout<<"\nSorted Data "; for (i = 0; i < n; i++) cout<<"->"<<arr[i]; return 0; }