user836087 user836087 - 3 months ago 12
Java Question

My Quick Sort implementation in Java is sorting only part of the array. Not sure why it's doing this

I wrote some code to learn the quicksort algorithm in java. I believe this should work the way I have it but I'm something here as the entire array does not get sorted correctly. I've reviewed this several times but have not gotten any luck. Thank you in advance for any insight you can provide on my code.

Below code returns a wacky output like this:


[9, 105, 45, 1, 19, 125, 125, 125, 125, 125, 1852, 1852, 180]


public static void main(String[] args) {
int[] arr = { 9, 105, 45, 1, 19, 1852, 3, 0, 66, 9, 2,125, 180 };
quickSort(arr, 0, 11);

System.out.println(Arrays.toString(arr));
}

public static void quickSort(int [] arr, int start, int end){
if(start < end){
int q = partition(arr, start, end);
quickSort(arr, ++start, q-1);
quickSort(arr, q+1, end);
}
}

public static int partition(int [] arr, int p, int r){
int x = arr[r];
int i = p - 1;
for(int j = p; j <= r-1; j++){
if(arr[j] <= x){
i++;
int ival = arr[i];
int jval = arr[j];
arr[i] = jval;
arr[j] = ival;

}
}
int rval = arr[r];
int i1val = arr[i + 1];
arr[r] = i1val;
arr[i] = rval;
return i + 1;
}

Answer

I can see three issues-

  1. The length of array is 13, but you are passing 11 as end index (should be 12)
  2. More importantly, there's problem with swap at the end of partition function. It should be arr[i+1] = rval, instead of arr[i] = rval.
  3. You don't need a while loop, nor do you need to increment and decrease start and end indices.

Corrected code is-

public static void main(String[] args) {
    int[] arr = { 9, 105, 45, 1, 19, 1852, 3, 0, 66, 9, 2,125, 180 };
    quickSort(arr, 0, 12);

    System.out.println(Arrays.toString(arr));
}

public static void quickSort(int [] arr, int start, int end){
    if(start < end){
        int q = partition(arr, start, end);
        quickSort(arr, start, q-1);
        quickSort(arr, q+1, end);
    }
}

public static int partition(int [] arr, int p, int r){
    int x = arr[r];
    int i = p - 1;
    for(int j = p; j <= r-1; j++){
        if(arr[j] <= x){
            i++;
            int ival = arr[i];
            int jval = arr[j];
            arr[i] = jval;
            arr[j] = ival;

        }
    }
    int rval = arr[r];
    int i1val = arr[i + 1];
    arr[r] = i1val;
    arr[i+1] = rval;
    return i + 1;
}

Edit : Turns out all this was pointed out in other answers while I was writing this one. I'm guess there's no harm leaving the answer here though.

Comments