quickSort.cpp

#include <iostream>
using namespace std;

int partition (int arr[], int low, int high)
{
    int pivot=low+rand()%(high-low+1);
    swap(arr[pivot],arr[high]);
    int i=low;
    for(int j=low;j<high;j++){
        if(arr[j]<arr[high]){
            swap(arr[i],arr[j]);
            i++;
        }
    }
    swap(arr[i],arr[high]);
    return i;
}

void randomQuickSort (int arr[], int low, int high)
{
    if(low>=high) return;
    int pivot=partition(arr,low,high);
    randomQuickSort(arr,low,pivot-1);
    randomQuickSort(arr,pivot+1,high);
}

int main() {
    srand(time(0));
	
    int len;
    cout<<"Enter length of array\n";
    cin>>len;
    
    int arr[len];
    cout<<"Enter values in array\n";
    for(int i=0;i<len;i++){
        cin>>arr[i];
    }
    
    randomQuickSort(arr,0,len-1);
    cout<<"Sorted array is\n";
    
    for(int i=0;i<len;i++){
        cout<<arr[i]<<" ";
    }
    cout<<"\nRandomized quick Sort-Best Time Complexity: O(nlogn)\n";
    
	return 0;
}