Java QuickSort Bugs

Question

I am working on a quick sort program for strings in an array, and I'm not sure what I'm doing wrong - it prints out the wrong answers.

    public static void quickSort(String[] s, int beg, int end){
    int i = beg, j = end;

    if(end-beg >= 1){ 
        String piv = s[beg];
        while(j > i){
            while(s[j].compareTo(piv) > 0 && j >= i && i >= beg)
                j--;
            while(s[i].compareTo(piv) <= 0 && j > i && i <= end)
                i++;
            if(j > i){
                String temp = s[i];          
                s[i] = s[j];     
                s[j] = temp;          
            }

            for(String k : s)
                System.out.print(k);
            System.out.println();

            quickSort(s, beg, j-1);
            quickSort(s, j+1, end); 

        }
    }

If I input {r, t, c, x, a, w, p} for example, I get r p c x a w t repeated 14 times. Please help!

Answer 1

Try this code:

private static void quickSort(String[] s, int beg, int end) {
    int i = beg, j = end;

    if (end-beg >= 1) {
        String piv = s[beg];
        while (j >= i) {
            while (s[i].compareTo(piv) < 0) {
                i++;
            }
            while (s[j].compareTo(piv) > 0) {
                j--;
            }
            if (j >= i) {
                String temp = s[i];
                s[i] = s[j];
                s[j] = temp;
                i++;
                j--;
            }
        }

        for(String k : s)
            System.out.print(k);
        System.out.println();

        quickSort(s, beg, j);
        quickSort(s, i, end);

    }
}

I tried to stick to your original implementation as much as possible. As Peter said, there are several things wrong with the original code, but if you compare the subtle differences I think it will make sense.

Answer 2

There are a number of problems here, you have used i where you meant j and j where you meant i at least twice. If you follow the inplace quick sort found on wikipedia you don't actually need to keep both an i and j. I would recommend starting from scratch and following wikipedia's puesdo code found below:

  // left is the index of the leftmost element of the subarray
  // right is the index of the rightmost element of the subarray (inclusive)
  // number of elements in subarray = right-left+1
  function partition(array, left, right, pivotIndex)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right]  // Move pivot to end
     storeIndex := left
     for i from left to right - 1  // left ≤ i < right
         if array[i] <= pivotValue
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1  // only increment storeIndex if swapped
     swap array[storeIndex] and array[right]  // Move pivot to its final place
     return storeIndex