Skip to content

Instantly share code, notes, and snippets.

@zarc1411
Created June 20, 2020 13:57
Show Gist options
  • Save zarc1411/81ea00cd67979789c574fa78cfab6903 to your computer and use it in GitHub Desktop.
Save zarc1411/81ea00cd67979789c574fa78cfab6903 to your computer and use it in GitHub Desktop.
Quick sort 3 partition
#include<bits/stdc++.h>
using namespace std;
pair<int , int> partition3(int arr[] , int l , int r){
pair<int , int> p;
int pivot = arr[l];
int high = l;
for(int i = l+1 ; i<=r; i++){
if(arr[i]<=pivot){
high++;
swap(arr[i],arr[high]);
}
}
swap(arr[l] , arr[high]);
int low = high;
for(int i = high-1 ; i>=l ; i--){
if(arr[i]==pivot){
--low;
swap(arr[low],arr[i]);
}
}
p.first = low;
p.second = high;
return p;
}
void quick3(int arr[] , int l , int r){
if(l>=r){
return;
}
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> distr(l, r);
int pivot = distr(gen);
swap(arr[l] , arr[pivot]);
pair<int , int> m = partition3(arr,l,r);
quick3(arr , l , m.first-1);
quick3(arr , m.second+1 , r);
}
int main(){
int n;
cin>>n;
int arr[n];
for(int i = 0 ; i<n ; i++){
cin>>arr[i];
}
quick3(arr , 0 , n-1);
for(int i = 0 ; i<n ; i++){
cout<<arr[i]<<" ";
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment