Logical error in a quicksort using a median of 3

Question

The instruction is to edit a quicksort program to select the median of three as the pivot as opposed to the first value of an array.

In order to do so, I've edited the code as follows:

public class medianOf3 {

        //Main method and test array 
        public static void main(String[] args) {

            int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
            quickSort(list);
            for (int i = 0; i < list.length; i++)
                System.out.print(list[i] + " ");
            System.out.println();
        }

        public static void quickSort(int[] list) {
            quickSort(list, 0, list.length - 1);
        }
        //The quicksort method 
        public static void quickSort(int[] list, int first, int last) {
            if (last > first) {
                int pivotIndex = partition(list, first, last);
                quickSort(list, first, pivotIndex - 1);
                quickSort(list, pivotIndex + 1, last);
            }
        }

       // Returns the median of three integers 
        public static int median(int first, int middle, int last) {
            return Math.max(Math.min(first, middle), Math.min(Math.max(first, middle), last));
        }

        //returns the index of a value 
        public static int  findIndex (int[] list, int t) { 
            if (list == null) return -1;
            int len = list.length;
            int i = 0;
            while (i < len) {
                if (list[i] == t) return i;
                else i=i+1;
            }
            return -1;
        }

    public static int partition(int[] list, int first, int last) {

        int middle = ((last-first) / 2)+first;    
        int pivot = median(list[first], list[middle], list[last]); // selecting the median of three (of the first, middle and last value) as the pivot
        int low = first +1; // Index for forward search
        int high = last; // Index for backward search
        int index = findIndex(list, pivot );

        int swap = list[index];
        list[index] = list[0];
        list[0] = swap;

        while (high > low) {

            // Search forward from left
            while (low <= high && list[low] <= pivot)
            low++;
            // Search backward from right
            while (low <= high && list[high] > pivot)
            high--;
            // Swap two elements in the list
                if (high > low) {
                int temp = list[high];
                list[high] = list[low];
                list[low] = temp;
                }
            }

        while (high > first && list[high] >= pivot)
        high--;

        // Swap pivot with list[high]

        if (pivot > list[high]) {
            list[first] = list[high];
            list[high] = pivot;
            return high;
        } else { return first;}
        }  

}

The above code returns the following output:

14 1 2 2 3 3 5 6 12 14

The desired output is this:

-2 1 2 2 3 3 5 6 12 14

Using the debugger, I'm able to get within one calculation of the array being sorted correctly, with only the last 2 values needing to be swapped:

-2 1 2 2 3 3 5 6 14 12

Within the final circulation at the

list[index] = list[0];

line of the partition method, is where the error occurs, using the debugger. I feel this is most likely a logical error but I'm uncertain of exactly what is going wrong at that point.

All feedback appreciated.

Answer 1

I suggest as solution (based in your code with few changes) :

public static void main(String[] args) {
    List<Integer> list = Arrays.asList(2, 3, 2, 5, 6, 1, -2, 3, 14, 12);
    quickSort(list, 0, list.size() - 1);
    System.out.println(list);
}

private static void quickSort(List<Integer> list, int first, int last) {
    if (last - first > 0) {
        int pivot = pivot(list, first, last);
        int index = partition(list, first, last, pivot);
        quickSort(list, first, index - 1);
        quickSort(list, index + 1, last);
    }
}

private static int pivot(List<Integer> list, int first, int last) {
    return ((last - first) / 2) + first;
}

private static int partition(List<Integer> list, int first, int last, int pivot) {
    Collections.swap(list, last, pivot);
    int j = first;
    for (int i = first; i < last; i++) {
        if (list.get(i) <= list.get(last)) {
            Collections.swap(list, i, j);
            j++;
        }
    }
    Collections.swap(list, last, j);
    return j;
}