Heap sort algorithm crashing after 4100 entries?

[ocprodigy]

Hi,

I developed the following heap sort algorithm code, and for some reason anytime it goes above 4100 entries, the algorithm completely crashes. It works perfectly up until that point but I can't see why it would crash?

void heap_from_root(MVector &v, int i, int n) {

		int end=n,j=0;

		// Identify the lowest root and how many sons it has. If it only has one son, set j=1.
		if (n==1) { n = 0; j = 1; }
		else if ((n-2) % 2 == 0) { n = (n-2)/2; }
		else if ((n-1) % 2 == 0) { n = (n-1)/2; j=1; }

		while (i <= n) { // Start from the lowest root, and go up until the highest root.

			if (j==0) { // If 2 sons, then check for the biggest value. If the biggest value is greater than root, exchange.

				if (v[2*n+1] > v[2*n+2] && v[2*n+1] > v[n]) { v.swap(2*n+1,n); }
				if (v[2*n+2] > v[2*n+1] && v[2*n+2] > v[n]) { v.swap(2*n+2,n); }
			
			}

			if (j==1) { // If 1 son, if the son's value is greater than the root, exchange.

				if (v[2*n+1] > v[n]) { v.swap(2*n+1,n); }
				j=0; // As only the last root can only have one son, set j to 0.
			
			}

			n--; // Go backwards to the next root.

		}

		/* The top value of the heap will now be the biggest value.	If the heap hasn't been completed sorted, 
		put the biggest value at the END of the heap, and restart the algorithm, this time excluding that last 
		value. Repeating this recursively will mean the heap will be sorted in ascending order. This saves using
		significant excess memory. */

		if (i < end) { v.swap(i,end); end--; heap_from_root(v,i,end); }

	}

	void heap(MVector &v) { heap_from_root(v,0,v.size()-1); }

Thank you in advance.

[MikeyBoy]

Have you tried running it in a debugger, to see exactly which line crashes on, and what the state of the memory is at that point?

[ocprodigy]

Hi, when I tried running it with VS 2010 debugger, I received the error:

Unhandled exception at 0x00f32db9 in Sorting.exe: 0xC00000FD: Stack overflow.

I'm quite new to C++ so I'm very unsure of how to proceed, it has pointed out the area:

	size_type size() const
		{	// return length of sequence
		return (this->_Mylast - this->_Myfirst);
		}

To be the problem on the second line. How would I go about sorting this?

[ne555]

http://www.cplusplus.com/forum/general/112111/

Look up the call stack.
¿what's a `MVector'?

[ocprodigy]

Sorry, this is the MVector class:

class MVector
{	
  // storage for the new vector class 
  vector<double> v;
  public:
    // constructor
    explicit MVector(){}
    explicit MVector(int n):v(n){srand(static_cast<unsigned>(time(NULL)));}
    explicit MVector(int n,double x):v(n,x){}
    // equate vectors;
    MVector& operator=(const MVector& X)
    {if(&X==this)return *this;v=X.v;return *this;}
    // access data in vector 
    double& operator[](int index){ return v[index]; }
    // access data in vector (const)
    double operator[](int index) const { return v[index]; }
    // size of vector
    int size() const {return v.size();}
	void push_back(double x){v.push_back(x);}
	void swap(int i,int j) { double c; c=v[i]; v[i] = v[j]; v[j] = c;  }
	void initialise_random(double xmin, double xmax) {
		const unsigned n = this->size();
		for(unsigned i=0;i<n;i++) {
			v[i] = xmin + rand()*(xmax - xmin) / static_cast<double>(RAND_MAX);
		}
	}

	bool cmp(int i, int j) { 
		if (v[i] < v[j]) { return true; } 
		else { return false; } 
	}
}; // end class MVector 

Not much the wiser when looking at the call stack?

> Sorting.exe!std::vector<double,std::allocator<double> >::size() Line 878 + 0x9 bytes C++
Sorry, this is all really baffling me.

[JLBorges]

> Unhandled exception at 0x00f32db9 in Sorting.exe: 0xC00000FD: Stack overflow.

Increase the maximum size to which the stack can grow.

Properties -> Configuration Properties -> Linker -> System -> Stack Reserve Size
Set this to (say) 0x800000 (ie. 8 MB)

http://msdn.microsoft.com/en-us/library/8cxs58a6(v=vs.100).aspx

[ne555]

> Sorting.exe!std::vector<double,std::allocator<double> >::size() Line 878 + 0x9 bytes C++
¿is that it? ¿who called `size()'?
By instance:

#0  MVector::size (this=0x7fffffffe250) at bar.cpp:23
#1  0x0000000000400e43 in MVector::initialise_random (this=0x7fffffffe250, xmin=0, xmax=1)
    at bar.cpp:27
#2  0x0000000000400c44 in main () at bar.cpp:64

we can see that `size()' was called inside `initialise_random()', invoked from `main()'

(maybe I should have said `look down the call stack' )

I cannot reproduce your problem, provide a testcase.


PS: ¿the order is O(n^2) ?