jeudi 21 septembre 2017

Choosing random Pivot in QuickSort partitioning takes more time, how is this possible?

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