In: Computer Science
I need a randomized quicksort function written in c++ or java with dual pivots and a partition function
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int partition(int* arr, int low, int high, int* lp);
void swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void Pivot(int* arr, int low, int high)
{
if (low < high) {
int lp, rp;
rp = partition(arr, low, high, &lp);
Pivot(arr, low, lp - 1);
Pivot(arr, lp + 1, rp - 1);
Pivot(arr, rp + 1, high);
}
}
int partition(int* arr, int low, int high, int* lp)
{
if (arr[low] > arr[high])
swap(&arr[low], &arr[high]);
int j = low + 1;
int g = high - 1, k = low + 1, p = arr[low], q = arr[high];
while (k <= g) {
if (arr[k] < p) {
swap(&arr[k], &arr[j]);
j++;
}
else if (arr[k] >= q) {
while (arr[g] > q && k < g)
g--;
swap(&arr[k], &arr[g]);
g--;
if (arr[k] < p) {
swap(&arr[k], &arr[j]);
j++;
}
}
k++;
}
j--;
g++;
swap(&arr[low], &arr[j]);
swap(&arr[high], &arr[g]);
*lp = j;
return g;
}
int main()
{
int n;
cout<<"enter the size of array"<<endl;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
Pivot(arr, 0, n);
cout << " array after sorting is: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}