Quicksort with middle element as the pivot

Question

I have been trying to implement a quicksort in Java, but I can't find a way to make it with a pivot as the middle element.

Array: String[] arr = {"D", "C", "B", "A", "A", "Z", "g", "F", "e", "d", "c", "b"};

Output: A A B C D F g Z b c d e

private static void quickSort(String[] arr, int start, int end) {
    if (end <= start) return;

    int pivot = partition(arr, start, end);
    quickSort(arr, start, pivot - 1);
    quickSort(arr, pivot + 1, end);
}

private static int partition(String[] arr, int start, int end) {
    String pivot = arr[start + (end - start) / 2];
    int i = start;
    int j = end;

    while (i < j)
    {
        if (arr[i].compareTo(pivot) < 0)
            ++i;
        
        else if (arr[j].compareTo(pivot) > 0)
            --j;

        else if (arr[i].equals(pivot))
            ++i;

        else if (arr[j].equals(pivot))
            --j;

        else
        {
            String temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    String temp = arr[i];
    arr[i] = pivot;
    arr[start + (end - start) / 2] = temp;

    return i;
}

When I do other arrays where elements smaller than the pivot are not on the right side, it works well. As in:

Array: String[] arr = {"D", "C", "B", "a", "A", "Z", "g", "f", "e", "d", "c", "b"};

Output: A B C D Z a b c d e f g

Any solutions?

Answer 1

The question's code is a mix of Hoare and Lomuto partition schemes. I changed the code to typical Hoare partition scheme that pre-increments and pre-decrements the indexes in partition().

    private static void quickSort(String[] arr, int start, int end) {
        if (end <= start) return;
        int pivot = partition(arr, start, end);
        quickSort(arr, start, pivot);     // not pivot-1
        quickSort(arr, pivot + 1, end);
    }

    @SuppressWarnings("empty-statement")
    private static int partition(String[] arr, int start, int end) {
        String pivot = arr[start + (end - start) / 2];
        int i = start-1;
        int j = end+1;
        while(true)
        {
            while (arr[++i].compareTo(pivot) < 0);
            while (arr[--j].compareTo(pivot) > 0);
            if(i >= j)
                break;
            String temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        return j;
    }

    public static void main(String[] args) {
        String[] arr = {"D", "C", "B", "a", "A", "Z", "g", "f", "e", "d", "c", "b"};
        int i;
        quickSort(arr, 0, arr.length-1);
        for(i = 1; i < arr.length; i++){
            if(arr[i-1].compareTo(arr[i]) > 0){
                break;
            }
        }
        if(i == arr.length)
            System.out.println("passed");
        else
            System.out.println("failed");
    }