mardi 24 septembre 2019

How do I take a random number as a pivot in a qicksort?

So I tested this code and it works if the pivot is the last element of the array, but if I try to run it with pivot being a random element the resulting array doesn't contain some of the elements of the original array

public static void quickSort(int[] S){
    int n = S.length;
    if(n<2)
        return;
    int random = (int)(Math.random() * n);

    int pivot = S[random];
    int m = 0, k = n;
    int[] temp = new int[n];

    for(int i = 0; i < n-1; i++){
        if(S[i] < pivot)
            temp[m++] = S[i];
        else if(S[i] > pivot)
            temp[--k] = S[i];
    } 
    int[] L = Arrays.copyOfRange(temp,0,m);
    int[] E = new int[k-m];
    Arrays.fill(E,pivot);
    int[] G = Arrays.copyOfRange(temp,k,n);
    quickSort(L);
    quickSort(G);
    System.arraycopy(L,0,S,0,m);
    System.arraycopy(E,0,S,m,k-m);
    System.arraycopy(G,0,S,k,n-k);
}

This code outputs 1 1 2 2 2 43




Aucun commentaire:

Enregistrer un commentaire