CODEWITHSUNDEEP
javaarrayssortingquicksort
terbubbs
terbubbs

Reputation: 1512

Implementing median-of-three into generic quicksort

I've been trying to implement median-of-three into this implementation of a quick-sort. I know this may not be the best implementation of a quick sort but unfortunately I am forced to work with this. 

public static <E extends Comparable<E>> void quickSort(E[] list){
    quickSort(list, 0, list.length - 1);
}

private static <E extends Comparable<E>> void quickSort(E[] list, int first, int last){
    if (last > first) {
        int pivotIndex = partition(list, first, last);
        quickSort(list, first, pivotIndex - 1);
        quickSort(list, pivotIndex + 1, last);
    }
}

private static <E extends Comparable<E>> int partition(E[] list, int first, int last){
    E pivot = list[first];
    int low = first + 1;
    int high = last;

    while (high > low) {
        while (low <= high && (list[low].compareTo(pivot) <= 0)){
            low++;
        }

        while (low <= high && (list[high].compareTo(pivot) > 0)){
            high--;
        }

        if (high > low){
            E temp = list[high];
            list[high] = list[low];
            list[low] = temp;
        }
    }

    while (high > first && (list[high].compareTo(pivot) >= 0)){
        high--;
    }

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

What I've done first is alter it to work with Generic arrays. Now I need to set the pivot to the median of the first three values in the list array.

I understand how to get the median of the first three values. What I don't understand is how it affects how this quick sort implementation works.

After setting the pivot to the median value, how does that affect the forward and backward searches? In the code shown, low is set to the "left" element incremented by 1. Would I increment the pivot value by 1 in my particular case? Can somebody explain the logic behind the particular median-of-three I am trying to implement?

Upvotes: 0

Views: 921

Answers (1)

rcgldr
rcgldr

Reputation: 28911

Usually with a Lomotu type scheme as seen in the example code, compare [low] with [middle] and [high] values and swap as needed so that the median value ends up at array[low]. This prevents worst case issues if sorting an already sorted or reverse sorted array. Using the median of the first 3 values would not prevent worst case for ordered or reversed ordered data.

With a Hoare type partition scheme, this is done by setting the pivot index to the middle of the array, and swapping with [low] and/or [high] as needed to end up with the median of 3 (low, middle, high) element at array[pivot].

Upvotes: 1

Related Questions