QuickSort descending order

Question

I am trying to implement QuickSort in a descending order. I have tried to trace through my code to see why it is only partially-sorted. My input was an int array of: {3,4,6,1,9,7}. After sorting, I got {9,4,7,6,3,1}, where 4 is not in the correct place.

    public int partition(int arr[], int left, int right)
    {
       int pivot = arr[right];
       int i = left - 1;
       for(int j = right; j >= left; j--)
    {
        if (arr[j] > pivot)
        {
            i = i + 1;                                      
            int temp = arr[i];
            arr[i]= arr[j];
            arr[j]= temp;
        }
    }

    int temp = arr[i+1];
    arr[i+1] = arr[right];
    arr[right] = temp;

    return i + 1;

    }

public void sorting(int arr[], int left, int right)
{
    if(left < right)
    {
        int q = partition(arr, left, right);
        sorting(arr, left, q - 1);
        sorting(arr, q + 1, right);
    }
}

Answer 1

Your code should look something like this:

public int partition(int arr[], int left, int right){
    int pivot = arr[left];
    int i = left;
    for(int j = left + 1; j <= right; j++){
        if (arr[j] > pivot){
            i = i + 1;
            int temp = arr[i];
            arr[i]= arr[j];
            arr[j]= temp;
        }
    }

    int temp = arr[i];
    arr[i] = arr[left];
    arr[left] = temp;

    return i;

}

public void sorting(int arr[], int left, int right){
    if(left < right)
    {
        int q = partition(arr, left, right);
        sorting(arr, left, q);
        sorting(arr, q + 1, right);
    }
}