CODEWITHSUNDEEP
c++functionrecursionstack-overflow
AverageProgrammer
AverageProgrammer

Reputation: 187

Stack overflow on recursive call of a function

I am trying to make a strand sort algorithm and when I try to recursive call it again it gives me stack overflow error

The recursive call is where I want to sort array a into two sorted arrays(preme, NoNpreme). And after that I merge these to back into a. I have tried to mess around with conditions and I figured out that array is sorted when there is only 1 element and that is my exit for recursion. But it doesn't work and I do not know why.

My algorithm:

int* urediSPrameni(int* a, int n)
{
    if (n <= 1)
        return a;

    int pe=a[0];
    int* preme = new int[n];
    preme[0] = a[0];
    int j = 1;
    int k = 0;
    int* NoNpreme = new int[n];
    for(int i=0;i<n;i++)
    {
        if (a[i] > pe)
        {
            pe = a[i];
            preme[j] = a[i];
            j++;
        }
        else
        {
            NoNpreme[k] = a[i];
            k++;
        }
    }
    NoNpreme = urediSPrameni(NoNpreme, k);


    // My merge algorithm:

    //Zlivanje
    int h = 0;//NoNpreme
    int s = 0;//Preme
    int i = 0;
    while (h < k && s < j)
    {
            if (preme[h] <= NoNpreme[s])
            {
                a[i] = preme[h];
                s++;
            }
            else
            {
                a[i] = NoNpreme[s];
                h++;
            }
            i++;
    }
    if (h > k)
    {
        for (int b = s;b < j;b++)
        {
            a[i] = NoNpreme[b];
            i++;
        }
    }
    else
    {
        for (int b = h;b < k;b++)
        {
            a[i] = preme[b];
            i++;
        }
    }
    return a;
}

I call function like this:

int n = 7;
int drek[] = { 5,1,2,20,5,28,7 };
int* urejenoZap = urediSPrameni(drek, n);
for (int i = 0;i < n;i++)
    cout << urejenoZap[i] << " ";
system("PAUSE");

Where drek is unsorted and urejenoZap is pointer to sorted array drek.

Upvotes: 0

Views: 128

Answers (1)

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32732

You assign the first element of a to pe, and store a copy of that element into preme. When sorting the elements of a into separate arrays based on which side of pe they fall on, you start with element 0 again (which you've already placed into preme), which, because if (a[i] > pe) will be false, will place this element into NoNpreme. Once the array reaches the point where there is more than one element, and the first element is the smallest, all of the elements will be copied into NoNpreme. Each recursive call after that will do the same, so the recursion will never end and you'll eventually run out of stack space.

The solution is to start your for loop with the second element:

for (int i = 1; i < n; i++)

Upvotes: 1

Related Questions