CODEWITHSUNDEEP
cquicksort
David
David

Reputation: 2721

Segfault with a quicksort implementation in C

I am debugging my code for a quick sort algorithm in C. It compiles but fails with a "Segmentation fault" when running it.

Can anybody help me to debug it and give me the working version of my code? I know there are existing and working ones on the internet. But what I really want is to find the bug of my own code. 

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);
}

Upvotes: 1

Views: 281

Answers (3)

Luchian Grigore
Luchian Grigore

Reputation: 258618

Your function will never exit.

It will keep calling itself until the call stack is full and cause a stack overflow exception.

The compiler should generate a warning for this:

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

You need an exit condition, something along the lines of:

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);
}

Also, make sure you call the function like:

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

the final parameter must be 1 less than the length of the array since C++ arrays are 0-based.

You also need one extra check in your while loops:

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

or else you might pass the end of the array.

Upvotes: 5

Daniel Fischer
Daniel Fischer

Reputation: 183888

In addition to the guaranteed stack overflow diagnosed by Luchian, you need to check that you don't run off the array in the inner loop:

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

Upvotes: 1

Ernest Friedman-Hill
Ernest Friedman-Hill

Reputation: 81694

Just looking at it quickly, I see a number of places where this could segfault. For example, here:

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

Imagine a list where key was, by chance, the largest element in the list. This loop will then run until head is past the end of the array, at which point a segfault can occur at any time. Likewise, the following loop can cause tail to move off the beginning of the array.

Upvotes: 3

Related Questions