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

Question

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

Possible duplicate of [Quick sort median selection](https://stackoverflow.com/questions/5605916/quick-sort-median-selection) — SSP, Sep 24 '19 at 19:25
On a side note, use variable names that are self-explanatory as a good programming practice. — Harshal Parekh, Sep 24 '19 at 19:28
You don't. You take a random *element* as the pivot. The pivot value has to be present in the data. — user207421, Sep 24 '19 at 21:39

score 0 · Accepted Answer · answered Sep 24 '19 at 20:14

0

The loop limit is not correct: i < n - 1. Thus you ignore the last element and, if it not greater than the pivot, it comes to the wrong part.

To fix it, you should include also the last element in the loop: i <= n - 1.

answered Sep 24 '19 at 20:14

mentallurg

4,570
5
25
34

@BeastMaster64: If the answer was helpful, you can mark it as helpful. – mentallurg Sep 26 '19 at 00:05

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

1 Answers1