Реализация Quicksort в C без использования нескольких массивов

Question

Я пытаюсь выяснить, как реализовать быстрый сортировку без необходимости создавать дополнительные массивы. Тем не менее, эта реализация работает только тогда, когда я использую 1 в качестве опоры. Программа seg неисправностей, когда я использую любой другой номер. Я не могу понять, какая переменная выходит за пределы, чтобы вызвать бесконечный цикл. Я был бы очень признателен за любую критику/помощь в этой функции.

void quick_sort(Item a[], int max, int pivot) 
{ 
    int i, j, p, t; 
    printf("%d", pivot); 
    if (max < 2) 
    { 
     return; 
    } 
    p = a[pivot]; 
    printf("%d", p); 
    for (i = 0, j = max-1;; i++, j--) 
    { 
     while (a[i] < p) 
     { 
      i++; 
     } 
     while (p < a[j]) 
     { 
      j--; 
     } 
     if (i >= j) 
     { 
      break; 
     } 
     t = a[i]; 
     a[i] = a[j]; 
     a[j] = t; 
    } 
    quick_sort(a, i, pivot); 
    quick_sort(a+i, max-i, pivot); 
} 

Answer 1

Ваша программа segfaulting, потому что если вы выбираете жесткий стержень, как, например, 2, если quick_sort вызывается в разделе только с 2 пунктами справа от массива, a[2] будет вне границ.

Я думаю, что лучшим вариантом для вашего решения является выбор стержня внутри функции, случайным образом или просто получение произвольного значения, например max/2. Вы просто должны быть уверены, что 0 <= pivot < max:

void quick_sort(int a[], int max) 
{ 
    int pivot = max/2; 
    int i, j, p, t; 
    if (max < 2) 
    { 
     return; 
    } 
    p = a[pivot]; 
    for (i = 0, j = max-1;; i++, j--) 
    { 
     while (a[i] < p) 
     { 
      i++; 
     } 
     while (p < a[j]) 
     { 
      j--; 
     } 
     if (i >= j) 
     { 
      break; 
     } 
     t = a[i]; 
     a[i] = a[j]; 
     a[j] = t; 
    } 
    quick_sort(a, i); 
    quick_sort(a+i, max-i); 
} 

Answer 2

Проблема заключается в этих двух строках:

quick_sort(a, i, pivot); 
quick_sort(a+i, max-i, pivot); 

Quicksort работает рекурсивно сортирует все меньшие и меньшие части массива. В конце концов, вы дойдете до точки, где в массиве есть только один элемент, который является базовым регистром рекурсии.

Проблема в том, что значение pivot передается по всем вызовам по мере того, как массив сжимается. Если опорный элемент имеет значение, отличное от 1, вы всегда будете вызывать переполнение (независимо от размера исходного массива).

Смещение должно быть выбрано внутри рекурсивная функция.