Аргументы для функции разделения для Quicksort

Question

Итак, я пытаюсь написать функцию quicksort на основе стека, которая вызывает функцию перегородки. Заголовок для раздела() заключается в следующем:

int partition(void **A, int n, void *pivot, int (cmp)(void *, void *)); 

, где А представляет собой массив, п является размером массива и поворот представляет собой значение шарнира (не индекс).

Мой текущий вызова раздела является:

partition(&A[low_int], high_int + 1, A[low_int+(high_int-low_int)/2], cmp) 

Выше, мои значения для низких и высоких являются классическим «л» и «з» используется в итерационной сортировке, где л начинается как самый низкий показатель (и h самый высокий). Эти значения затем изменяются по мере продолжения функции.

я выложу свою функцию секционирования ниже:

int 
partition(void **A, int n, void *pivot, int (cmp)(void *, void *)) { 
    int k; 

    int i = 0; 
    for (int j = 0; j <= n-2; j++) { 
     if (cmp(A[j], pivot) <= 0) { 
      i++; 
      swap(A, i, j); 
     } 
    } 
    swap(A, i+1, n-1); 
    k = i + 2; 
    return k; //k is the first value after the pivot in partitioned A 

}

Моя проблема заключается в принятии решения о входах для моего вызова раздела(). Для первого аргумента я выбрал & [low_int], так как я не использую «левый» как один из моих входов и поэтому пытаюсь создать указатель, чтобы по существу запустить мой массив позже. Третий аргумент, если для pivot, где я пытался выбрать элемент в этом диапазоне, но оба этого и аргумент 1 заставляют мой код либо возвращать несортированный массив, либо работать бесконечно.

Могу ли я, пожалуйста, помочь мне с тем, что я сделал неправильно, и как его исправить?

Я попытался включить весь соответствующий код, но, пожалуйста, дайте мне знать, если я пропустил что-либо важное или если что-либо, что я написал, неясно или вам нужно больше информации. Спасибо

Answer 1

Рассмотрим, что произойдет, если low_int 1000 и high_int является 2000 и массив заканчивается в 2000. Теперь вы даете ему массив B = &A[1000] и значение 2001. Значение 2001 заставляет его доступ к элементу B[2001-1] = B[2000] = A[3000]. Он обращается к массиву за пределами границ.

Разве вы не должны использовать что-то наподобие high_int - low_int + 1 для второго аргумента? Примечание. Я не подтвердил, что ваш код не имеет ошибок с аргументами high_int - low_int + 1, но в любом случае мне кажется, что вы должны вычесть low_int от high_int.

Другим вариантом было бы дать его A, low_int и high_int.