Обнаружена бесконечная петля в быстрой сортировке (hoare), но я не вижу проблемы

Question

Итак, я написал алгоритм быстрой сортировки и алгоритм разбиения хора.Каким-то образом, когда я пытаюсь запустить пример case в main (), он зависает на quickSort (test, 0,3).Кажется, есть бесконечный цикл.Я не вижу, как это исправить, так как две функции по отдельности кажутся нормальными.

Я попытался отладить, но я довольно плохо знаком с c.Я заметил, что quickSort (test, 0,3) вызывает себя рекурсивно.Так что я знаю, что проблема связана с высоким, а не уменьшением.Но я взял пример псевдокода с университетского слайда, чтобы создать функцию, и все, кажется, выстраивается.

void printArray(int A[], int high) {
    for (int i=0; i<=high; i++) {
         printf("%d ", A[i]);
    }
}

int partitionHoare(int A[], int low, int high) {
    int pivot=A[low];
    int left = low-1;
    int right= high+1;

    while (1){
        while (1){
            left++;
            if (A[left]>=pivot) break;
        }
        while (1){
            right--;
            if (A[right]<=pivot) break;
        }


        if (left<right)  {
            int temp=A[left];
            A[left]=A[right];
            A[right]=temp;
        }
        else return left;
    }
}

void quicksort(int A[], int low, int high){
    if (low<high){
        int middle=partitionHoare(A,low, high);
        quicksort(A, low,middle-1);
        quicksort(A, middle, high);
    }
}


void main (){
    int test[]={64,81,24,42,90,30,9,95};
    quicksort(test,0,7);
    printArray(test,7);

Я действительно ожидаю, что тестовый массив будет распечатан следующим образом: «9, 24, 30, 42, 64, 81, 90, 95»

Answer 1

У вас логический недостаток в функции quicksort():

void quicksort(int A[], int low, int high){
    if (low<high){
        int middle=partitionHoare(A,low, high);
        quicksort(A, low,middle-1);
        quicksort(A, middle, high);
    }
}

Это не гарантирует, что рекурсия прекратится.

В частности, если в некотором подмассиве длиной больше 1 первый элемент является наименьшим и не является дубликатом, то partitionHoare() вернет значение, равное low, без изменения массива. В этом случае рекурсивный вызов для левого подмассива ничего не будет делать, но рекурсивный вызов для right подмассива точно повторяет текущие аргументы. Ничего не изменившись, гарантируется, что то же самое произойдет снова и снова, на неопределенный срок.

В этом случае вы можете прервать бесконечную рекурсию, проверив в quicksort(), действительно ли middle == low, но это не даст вам правильной сортировки.

Одно общее решение здесь двоякое:

1. Убедитесь, что функция секционирования меняет значение сводки на индекс сводки, который она сообщает. Это наверняка будет правильная конечная позиция для этого значения.
2. При повторении исключите сводный индекс (значение которого мы знаем как правильное) из обоих подмассивов, так что каждая подзадача наверняка будет меньше, чем родительская проблема.

Answer 2

Изменить раздел, чтобы вернуться вправо (вместо левого). Измените два рекурсивных вызова на | быстрая сортировка (А, низкий, средний); | быстрая сортировка (A, средний + 1, высокий) ;. Это будет в точности соответствовать примеру статьи в вики:

https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

Возможно, вы захотите изменить название «середина». Пример Wiki называет это p значением индекса разбиения раздела (в отличие от значения индекса для оси), поскольку при схеме разбиения Hoare элемент и элементы, равные оси, могут заканчиваться в конце левого раздела и / или в начале правильный раздел.