Код разделения Hoare, используемый в Quicksort (ссылка на книгу Кормена), переходит в бесконечный цикл

Question

Я кодирую Quicksort, используя разделение Hoare из книги Cormen Algorithms. Я не могу обнаружить никаких ошибок в своем коде, и он выглядит так же, как псевдокод в книге.

swapping i, j : 0, 8
-2 2 -5 -3 6 0 1 0 -1 4

swapping i, j : 1, 3
-2 -3 -5 2 6 0 1 0 -1 4
p is: 2

swapping i, j : 0, 1
-3 -2 -5 2 6 0 1 0 -1 4
p is: 0

После того, как это сделало вышеупомянутые перестановки, этот код в конечном итоге заканчивает разбиение на подмассив {-3, -2}, За это subarrayПивот -3 и partition() returns 0 как index (j), Так как этот подмассив уже отсортирован с помощью pivot -3 в 0th index положение, никаких изменений не делается каждый раз, когда это быстро сортируется. Так что qsort зацикливается навсегда.

Может кто-нибудь сказать мне, как это отличается от раздела Hoare в книге, и если так же, почему это не работает?

void swap(int *a, int i, int j) {
        cout << "swapping i, j : " << i << ", " << j << endl;
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp; }

int partition(int *a, int len) {
        int pivot = a[0];

        int i = -1, j = len;
        while (true) {
               while ( ++i && a[i] < pivot && i< j) {}
               while (--j && a[j] > pivot && i <j) {}
               if (i < j )
                  swap(a, i, j);
               else 
                  return j ;
        } }

void qsort(int a[], int len) {
        int p = partition(a, len);
        cout << "p is: " << p << endl;
        qsort(a, p);
        qsort(a+p, len - p ); }

int main(int argc, char *argv[]) {
        int a[10] = {-1, 2, -5, -3, 6, 0, 1, 0, -2, 4};
        qsort(a, 10); }

Answer 1

Расширяя мой комментарий в ответе, partition() возвращает индекс на основе 0, но вам нужно передать длину массива (длина на основе 1) в qsort()так и должно быть:

void qsort(int a[], int len)
{
    int p = partition(a, len);
    cout << "p is: " << p << endl;
    qsort(a, p + 1); // note p+1 instead of p
    qsort(a + p + 1, len - (p + 1)); // note p+1 instead of p
}

Пробный забег будет выглядеть так:

swapping i, j : 0, 8
-2 2 -5 -3 6 0 1 0 -1 4

swapping i, j : 1, 3
-2 -3 -5 2 6 0 1 0 -1 4
p is: 2

Теперь вы должны позвонить qsort(a, 3) так как вы хотите отсортировать под-массив -2 -3 -5, Кроме того, qsort(a+3, 7) для подмассива 2 6 0 1 0 -1 4