1

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 wacky values are returned from the code.

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

2
  • 2
    Have you stepped through your code with a debugger? Commented Aug 25, 2016 at 19:53
  • 1
    There are 13 elements in your array. Maybe use Array.length to avoid counting problems. Commented Aug 25, 2016 at 20:02

3 Answers 3

3

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 guess there's no harm leaving the answer here though.

Sign up to request clarification or add additional context in comments.

Comments

3

The biggest problem in your code is located at the bottom of the partition method:

int rval = arr[r];
int i1val = arr[i + 1];
arr[r] = i1val;
arr[i] = rval; // <-- here

You're setting i1val to arr[i + 1], but then you set arr[i] to rval instead of setting arr[i + 1] to rval.

Fixing this, along with the array length problem mentioned in Boris the Spider's comment, should fix your code.

2 Comments

to add onto this, the code could probably be made a lot cleaner by having a look at the pseudocode on wikipedia. There are a lot of -1's and +1's everywhere currently in an attempt to make things work, but those easily cause these off-by-one errors.
@DennisSoemers agreed, as well as using descriptive variable names and only using one temporary variable when swapping.
0

The quicksort method should have an if instead of a while. I did not check the rest of the code yet, but that part is definitely wrong. The recursive calls should already make sure you keep going till it's sorted, there is no need for an additional loop around that.

2 Comments

sorry that was a typo. I changed it
Yea the whole thing was the wrong code and output. I just updated it and also took some recomendations. It's returning the following now: [9, 105, 45, 1, 19, 125, 125, 125, 125, 125, 1852, 1852, 180]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.