-1
RecursiveSort::RecursiveSort(int myArray[], int first, int arraySize)
{
    int smallest = first, j;

    if (smallest < arraySize)
    {   
        smallest = first;
        for (j=first+1; j<arraySize; j++)
        {
            if (myArray[j] < myArray[smallest])
            {
                smallest = j;
            }
        }
        swap(myArray[first], myArray[smallest]);
        first++;
        RecursiveSort::RecursiveSort(myArray, first, arraySize);
    }
};

and in my main(); i will call RecursiveSort sort(myArray, 0, arraySize);

There is a stack overflow when arraySize > 4000, and the program crashes. Is it possible to call class destructors somewhere to prevent stack overflow? I have tried using "release" instead of "debug" (project properties > configuration manager > configuration pull-down menu). However this causes other issues when I try to integrate a "TimeStamp_Lib.lib" library which is used to measure how long the sort takes.

Any advice/suggestions would be greatly appreciated, thank you!

billy
  • 1

3 Answers3

2

You should make this a free function, so no objects would be created. If, for some reason the algorithm has to run in a constructor of a class, you can call it from the constructor.

That said, unless the compiler optimizes the recursion into iteration itself, recursion won't be suitable for algorithms that require going that deep. To sort 4000 integers, your function goes 4000 levels deep which eats a lot of stack space. By comparison, a quick sort goes some log2(4000) = 12 levels deep.

visitor
  • 1,781
  • 10
  • 7
1

There are no allocations in that function - your issue is not that you have allocated too much memory.

I'd imagine you are recursing too many times. That will require some form of algorithm change, or just a limit on how many items you can sort with this method. If you can change this in such a way that the compiler can optimise away the recursion, that would work (though it could be implementation specific). Even better, remove the recursion yourself and change it to a stack-based loop. Here's some more information about that

Community
  • 1
  • 1
Ayjay
  • 3,413
  • 15
  • 20
0

Yes, destructors can be manually invoked. However, they destroy an object, they don't free its memory. Recursion is easy to think in terms of, but its not so useful in real life. Try moving all your objects to a pool outside the stack, or better yet work in an iterative way.

K-ballo
  • 80,396
  • 20
  • 159
  • 169
  • Exactly how and where would I move my objects to a pool outside the stack? My homework assignment is to write 2 algorithms of selection sort, one using iteration and the other using recursion. So unfortunately I will have to figure out a way to prevent stack overflow :( – billy Oct 05 '11 at 02:45
  • 2
    @billy: Why is your function declared as a class constructor? – K-ballo Oct 05 '11 at 02:50
  • should i use 'RecursiveSort.RecursiveSort' instead? – billy Oct 05 '11 at 02:53
  • @billy: You should write your function as a function instead. – K-ballo Oct 05 '11 at 03:01