What is wrong with this quicksort?

Question

I am reviewing topics for a programming interview,

and started doing some algorithms. I've written this quicksort, out of a pseudo code from a book.

Its exactly the same, but it does not work. It does compile and runs without a problem.

Any help would be appreciated.

    public static void quicksort(int [] array , int i, int j){

       if (i<j) {
            int p= partition(array, i, j);
            quicksort(array,i,p-1);
            quicksort(array,p+1,j);
      }

    }
    public static int partition(int [] array, int i, int j){

    int val= array[i];
    int h= i;
    for (int k = i+1; k<j; k++) {
        if (array[k]<val) {
            h++;
            swap(array,h,k);
        }
        swap(array,i,h);
    }
   return h;

}
  public static void swap (int a[],int indexa, int indexb){

    int aux= a[indexa];
    a[indexa]=a[indexb];
    a[indexb]=aux;

}

In main:

    int [] a= new int[]{1,3,17,5,6,7,11,19,4,2,15,8,13,15,9,14,12,16,18,10};
    quicksort(a,0,a.length-1);

Actual text from book

https://www.dropbox.com/s/gzxb8ezvryrq6ox/2014-02-27%2022.04.56.jpg

https://www.dropbox.com/s/1kmavnvzbrvp7xg/2014-02-27%2022.05.05.jpg

Answer 1

I have rewritten your codes and add some message between the calls.

First change:

for (int k = startIndex + 1; k < endIndex; k++)

to

for (int k = startIndex + 1; k <= endIndex; k++)

Second change: Move the swap call outside the for loop in partition

public static void main(String args[]) {
        int[] array = { 1, 3, 17, 5, 6, 7, 11, 19, 4, 2, 15, 8, 13, 15, 9, 14, 12, 16, 18, 10 };
        System.out.println(Arrays.toString(array));
        quicksort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }

    public static void quicksort(int[] array, int startIndex, int endIndex) {
        System.out.println("quicksort(" + Arrays.toString(array) + ", " + startIndex + ", "
                + endIndex + ")");
        if (startIndex < endIndex) {
            int p = partition(array, startIndex, endIndex);
            quicksort(array, startIndex, p - 1);
            quicksort(array, p + 1, endIndex);
        }
    }

    public static int partition(int[] array, int startIndex, int endIndex) {
        System.out.println("partition(" + Arrays.toString(array) + ", " + startIndex + ", "
                + endIndex + ")");
        int startValue = array[startIndex];
        int h = startIndex;
        for (int k = startIndex + 1; k <= endIndex; k++) {
            if (array[k] < startValue) {
                h++;
                swap(array, h, k);
            }
        }
        swap(array, startIndex, h);
        return h;
    }

    public static void swap(int a[], int indexa, int indexb) {
        System.out.println("Before Swap: " + Arrays.toString(a));
        System.out.println(a[indexa] + " <-> " + a[indexb]);
        int aux = a[indexa];
        a[indexa] = a[indexb];
        a[indexb] = aux;
        System.out.println("After Swap: " + Arrays.toString(a));
    }

Output is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 15, 16, 17, 18, 19]