Thread: Need help with quick sort algorithm

Hello

I tried to program a quick sort algorithm with a pre-defined array. As I was ready and tried to run the program I got a stack overflow.

Can someone help me with this problem and maybe tell me the cause?

Code:

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>

int partition(int *A, int start, int end)
{
    int i, hilf;
    int pivot;
    int pIndex;
    pivot = A[end];
    pIndex = start;

    for(i=start; i<end; i++)
    {
        if(A[i]<=pivot)
        {
            hilf=A[pIndex];
            A[pIndex]=A[i];
            A[i]=hilf;
            pIndex++;
        }
    }
    hilf=A[pIndex];
    A[pIndex]=A[end];
    A[end]=hilf;
}

void sort (int *A, int start, int end)
{
    int pIndex;
    pIndex = partition(A, start, end);
    sort(A, start, pIndex-1);
    sort(A, pIndex+1, end);
    return;
}

int main()
{
    int i;
    int A[] = {7,3,2,6,4,1,5,8};
    sort(A,0,7);

    for(i=0;i<8;i++)
        printf("%4d", A[i]);
    getch();
    return 0;
}

Every recursion must have a base case -- as it stands you call sort, which calls sort twice, which calls sort four times, which calls sort eight times, which ...... You'll need to decide when you are "done" with a subarray.

Originally Posted by tabstop

Every recursion must have a base case -- as it stands you call sort, which calls sort twice, which calls sort four times, which calls sort eight times, which ...... You'll need to decide when you are "done" with a subarray.

Thanks a lot

Code:

void sort (int *A, int start, int end)
{
    int pIndex;
    if (start < end)
    {
    pIndex = partition(A, start, end);
    sort(A, start, pIndex-1);
    sort(A, pIndex+1, end);
    }
    return;
}

That was the missing condition.