Quicksort algorithm not working in Java

Question

I have a pseudo code of a Quicksort in my book, that I am following step-by-step. But the end output is not what I want. I have turned it into this code:

public class quickSort {

    public int[] quick(int[] A, int p, int r){
        int q;
        if(p<r){
            q = partition(A, p, r);
            //First partition comfirmed to "work"
            quick(A, p, q-1);
            quick(A, q+1, r);
        }
        return A;
    }

    public int partition(int[] A, int p, int r){

        int x = A[r];
        int i = p-1;
        int temp;

        for(int j=p; j<r-1; j++){
            if(A[j]<=x){
                i = i+1;
                temp = A[i];
                A[i] = A[j];
                A[j] = temp;
            }
        }
        temp = A[i+1];
        A[i+1] = A[r];
        A[r] = temp;

        return i+1;
    }

}

My book illustrates how the first partition is being handled. With the input:

2 8 7 1 3 5 6 4  

.. the first partition "sorts" this into

2 1 3 4 7 5 6 8  

.. and this I have comfirmed. And so, if this work, and it is just calling itself with smaller parts to do the exact same thing, why is it in the end giving the output:

2 3 1 4 5 7 8 7  

.. and not something that is sorted???

Answer 1

The error is that only elements [p, r-2] are going to be processed in public int partition() instead of [p, r-1]. A[r-1] might happen to be less than pivot, but it is not swapped and stays in its place

Answer 2

Alright so here's your answer tweaked and it works:

import java.util.Arrays;

public class QuickSort
{
  public QuickSort()
  {
    int array[] = { 2, 8, 7, 1, 3, 5, 6, 4 };
    quickSort(array, 0, array.length - 1);

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

  void quickSort(int[] array, int p, int r)
  {
    if (p < r)
    {
      int q = partition(array, p, r);
      quickSort(array, p, q - 1);
      quickSort(array, q + 1, r);
    }
  }

  int partition(int array[], int p, int r)
  {
    int x = array[r];
    int i = p - 1;

    for (int j = p; j < r; j++)
    {
      if (array[j] <= x)
      {
        i += 1;

        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }
    }

    int temp = array[i + 1];
    array[i + 1] = array[r];
    array[r] = temp;

    return i + 1;
  }

  public static void main(String[] args)
  {
    new QuickSort();
  }
}

But by now I'm sure you got to know what went wrong. I had to keep my word though and that's why I'm updating my answer here.

Answer 3

it should be for(int j=p; j<=r-1; j++)

public int partition(int[] A, int p, int r){

int x = A[r];
int i = p-1;
int temp;

for(int j=p; j<=r-1; j++){
    if(A[j]<=x){
        i = i+1;
        temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }       
}
temp = A[i+1];
A[i+1] = A[r];
A[r] = temp;

return i+1;

}