Quicksort Algorithm not assigning pivot correctly

java, quicksort, sorting

Solution

I had to get rid of partition, because you need both `i` and `j`. It should look like this:

public void quickSort(int[] a, int left, int right) {

    int i = left; // Was -1 
    int j = right; // Was +1
    int pivot = a[left + (right - left) / 2]; // Pivot is the value of the middle index, not the index itself
    while (i <= j) { // Changed terminating condition
        //   i++;  Not needed
        while (a[i] < pivot) { 
            i++;
        }
        //    j++; Not needed
        while (a[j] > pivot) {
            j--;
        }
        if (i <= j) {  // Changed terminating condition
            swap(a, i, j);
            i++;  // You need to progress the indexes after the swap
            j--;
        }
    }

    System.out.println(Arrays.toString(a));
    if (left < j) {  // Changed condition
        quickSort(a, left, j);
    }
    if (i < right) { 
        quickSort(a, i, right); // was i + 1
    }
}

Output:

[4, 5, 1, 2, 3, 7, 6, 8]
[1, 5, 4, 2, 3, 7, 6, 8]
[1, 3, 2, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]

Problem

I watched this fantastic visualization of a quick sort algorithm: http://www.youtube.com/watch?v=Z5nSXTnD1I4 I felt I really understood the principles behind quick sort and, with the help of some guides online, set about creating my own quick sort. This is what I came up with: ``` public void quickSort(int[] a, int left, int right) { int index = partition(a, left, right); if (left < index - 1) quickSort(a, left, index); if (index < right) quickSort(a, index + 1, right); } private int partition (int[] a, int left, int right) { int i = left - 1; int j = right + 1; int pivot = a[0]; while (i < j) { i++; while (a[i] < pivot) i++; j--; while (a[j] > pivot) j--; if (i < j) swap (a, i, j); } return i; } private void swap (int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } ``` The values of left and right are the following: ``` left = 0 right = array size - 1 ``` Unfortunately the output isn't correct. The problem appears to lie in my treatment of the pivot. In the visualization I watched, the instructor physically removed the pivot and left the pointer pointing at nothing. He carried on with the tutorial and when he got to the point where i and j (what I call left and right) both pointed at the same empty spot, he inserted the pivot and carried on. As I am physically keeping the pivot in place, I am finding it difficult to properly sort it. In this code, I am working with the input: ``` 4 8 1 6 3 7 2 5 ``` I get the output: ``` 1 3 2 6 8 7 4 5 ``` Once the "4" value (i.e. the pivot) is sorted at the very start of the algorithm, I never resort it, which throws everything off. Additionally, I think there is something wrong with the quickSort method. Could someone give me a few pointers? Thanks. Edit: Two edits that were here have been removed as they contained unnecessary and incorrect information. One of them changed the pivot to: (left + right) / 2. This was of course wrong for the reasons explained in the answers below.

Original source