Быстрая сортировка по убыванию

Question

Я пытаюсь реализовать QuickSort в порядке убывания.Я попытался проследить мой код, чтобы понять, почему он только частично отсортирован.Мой вход был массивом из: {3,4,6,1,9,7}.После сортировки я получил {9,4,7,6,3,1}, где 4 не в нужном месте.

    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

Ваш код должен выглядеть примерно так:

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);
    }
}