public static int partitionsimple_hoare(int[] arr,int l , int h){
int pivot = arr[l];
int i = l-1;
int j = h+1;
while(true){
do{
i++;
}while(arr[i]<pivot);
do{
j--;
}while(arr[j]>pivot);
if(i<j){
swap(arr,i,j);
}
else break;
}
return j;
}
This is the basic implementation of Quicksort partition which I employed.
but when I replace the first line (choosing pivot), with :
int pivot = arr[randomPivot(l,h)];
where, the implementation is this:
public static int randomPivot(int l, int r){
int x =(int)( Math.random()*(r-l+1));
return x+l;
}
It surprisingly takes a lot more time. (i measured time between the sort call with System.nanoTime(); This isn't supposed to happen. Is it due to Java's Math.random() taking more time than it should've ideally taken?
Aucun commentaire:
Enregistrer un commentaire