Segfault с быстрой реализацией в C

Question

Я отлаживаю свой код для алгоритма быстрой сортировки на языке C. Он компилируется, но при его запуске происходит сбой "Ошибка сегментации".

Может кто-нибудь помочь мне отладить его и дать рабочую версиюмой код?Я знаю, что существуют и работают в Интернете.Но я действительно хочу найти ошибку в моем собственном коде.

void myQuickSort(int list[],int head, int tail)
{
    int m = head;
    int n = tail;

    int key = list[m];
    ++head;
    while(head < tail)
    {
        while(list[head] < key)
        {
            ++head;
        }
        while(list[tail] >= key)
        {
            --tail;
        }
        //swamp two elements, to divide the array to two groups
        int temp = list[head];
        list[head] = list[tail];
        list[tail] = temp;

    }

    //get the pivot element in dividing position
    int temp = list[m];
    list[m] = list[head];
    list[head] = temp;

    myQuickSort(list, m, head-1);
    myQuickSort(list, head+1, n);
}

Answer 1

Ваша функция никогда не завершится.

Он будет продолжать вызывать себя до тех пор, пока стек вызовов не заполнится и не вызовет исключение переполнения стека.

Компилятор должен сгенерировать предупреждение для этого:

warning C4717: 'myQuickSort' : recursive on all control paths, function will cause runtime stack overflow

Вам нужно условие выхода, что-то вроде:

void myQuickSort(int list[],int head, int tail)
{
    //exit condition, or else the function will always call itself
    if ( head >= tail )
       return;

    /**
    ...
    */

    myQuickSort(list, m, head-1);
    myQuickSort(list, head+1, n);
}

Кроме того, убедитесь, что вы вызываете функцию как:

int num[5] = {1,4,2,3,5};
myQuickSort(num,0,4);

конечный параметр должен быть на 1 меньше длины массива, поскольку массивы C ++ основаны на 0.

Вам также нужна дополнительная проверка в циклах while:

 while( head < tail && list[head] < key )  // see if head reached the end
 {
     ++head;
 }
 while( head < tail && list[tail] >= key )
 {
     --tail;
 }

или вы можете передать конец массива.

Answer 2

Просто глядя на это быстро, я вижу ряд мест, где это может привести к сбою.Например, здесь:

while(list[head] < key)
    {
        ++head;
    }

Представьте список, где key был, случайно, самым большим элементом в списке.Этот цикл будет выполняться до тех пор, пока head не выйдет за конец массива, и в этот момент в любой момент может произойти ошибка.Аналогично, следующий цикл может заставить tail сдвинуться с начала массива.

Answer 3

В дополнение к гарантированному переполнению стека, диагностированному Лучианом, вам необходимо убедиться, что вы не запускаете массив во внутреннем цикле:

while(head <= tail && list[head] < key)
while(head <= tail && list[tail] >= key)