Hi, everyone.

I am doing a performance test on the heapsort. I wrote this program and it has a run-time error that I cannot explain. I am compiling on Microsoft Visual Studio 2008 and this is the error.

HEAP CORRUPTION DETECTED after Normal Block ... well, I think that the details are not necessary for the rest of the problem.

This is the problem. I am allocating a dynamic array (int* a = new int). I am passing it to the heapsort (Heapsort(A, size)). This is the signature of this function:

void Heapsort(int A[], unsigned int N).

It takes an array and the size of the array and it makes the sort inside the array. A is a reference to the passed array.

And further, in the main(), when I do this: delete[] A, it launches the error window with the message I described above.

I am not able to explain what happened. Passing the dynamic array to an function that has A[] as a parameter has transformed it into an automatic array? I'm running out of ideas, here.

Can someone explain me what is the problem? This is the complete code:

#include <iostream>
#include <time.h>
#include <string>
#include <fstream>
#include <stdio.h>

using namespace std;

void Swap(unsigned int i, unsigned int j, int A[])
{
	int z= A[i];
	A[i] = A[j];
	A[j] = z;
}

unsigned int Right(unsigned int i)
{
	return 2 * i + 1;
}

unsigned int Left(unsigned int i)
{
	return 2 * i;
}

void Sift(unsigned int p, unsigned int q, int A[])
{
	unsigned int k, l = Left(p), r = Right(p);

	if (l <= q && A[l] > A[p])
		k = l;
	else
		k = p;

	if (r <= q && A[r] > A[k])
		k = r;

	if (k != p)
    {
		Swap(k, p, A);   
		Sift(k, q, A);
    }
}

void Heapsort(int A[], unsigned int N)
{
	unsigned int r = N / 2 + 1;

	while (r > 1)
    {
        r = r - 1;
        Sift(r, N, A);
    }
      
	r = N;
	while (r > 1)
    {
        Swap(1, r, A);
        r = r - 1;    Sift(1, r, A); 
    }
}

#define DEBUG 0

int main()
{
	//Function declarations.
	int Nothing();
	int createList(int*&, bool, bool, int);

	srand(clock());   //Initializes the pseudo-random generator;

	const int NUMBER_OF_TIMES_FOR_CLOCK = 5;   //IMPORTANT: Number of times to repeat the test, to eliminate the possible clock error.
	const int NUMBER_OF_NEEDED_DOTS = 1000; 
	const int MAX_SIZE_OF_ARRAY = 100000;
	const int FREQUENCY_FOR_PROGRESS = 100;
	const std::string NAME_OF_OUTPUT_FILE = "heapsortresult.txt";   //Where we will print the results.

	clock_t initialTime = 0;
	clock_t finalTime = 0;
	clock_t runningTime = 0;
	clock_t uselessTime = 0;

	std::ofstream out(NAME_OF_OUTPUT_FILE.c_str());

	int dotCounter = 0;     //Variable that controls the number of dots written in the file.

	//While we don't have enough dots for the graph...
	for (; dotCounter < NUMBER_OF_NEEDED_DOTS; ++dotCounter)
	{
		int* A = 0;        //The array that will contain the numbers to sort.
		int* ref = 0;      //The array that will be used to reset A at each end of sort (because we need to repeat the sort...)
		int* dummyArr = 0; //The array that will be used to substract the affectation time.
		int size;          //The size of A.

		size = createList(ref, true, false, MAX_SIZE_OF_ARRAY);   //We create the array and we will obtain its size.

		A = new int[size];
		//We set A before the first sort...
		for (int i = 0 ; i < size; ++i)
		{
			A[i] = ref[i];
		}

		int loopCount = 0;      //Variable that counts the number of times we do the same treatment.

		//Start counting!
		initialTime = clock();

		while (loopCount != NUMBER_OF_TIMES_FOR_CLOCK)
		{
			//IMPORTANT: Put treatment between the two commentary lines.
			//------------------------------------------------
			Heapsort(A, size);

			//WARNING: We will need to substract all the time of the treatment below.
			for (int i = 0; i < size; ++i)
			{
				A[i] = ref[i];
			}
			//------------------------------------------------

			++loopCount;
		}

		//End counting!
		finalTime = clock();

		runningTime = finalTime - initialTime;  //runningTime is the number of ticks

		loopCount = 0;   //We reset the loop count, to eliminate all unnecessary time.

		if (DEBUG)
			printf("About to allocate a dummy array of size %d\n", size);

		dummyArr = new int[size];     //We need a dummy array, to eliminate all the time wasted by resetting A.

		if (DEBUG)
			printf("After allocating a dummy array of size %d\n", size);

		//Start counting!
		initialTime = clock();

		//Null job to eliminate all unneccesary time.
		while (loopCount != NUMBER_OF_TIMES_FOR_CLOCK)
		{
			Nothing();     //because of branching to heapSort  
			for (int i = 0; i < size; ++i)    //because of the resetting of A.
			{
				dummyArr[i] = ref[i];
			}
			++loopCount;   //because of the increment.
		}

		//Finish counting!
		finalTime = clock();

		uselessTime = finalTime - initialTime;
		finalTime = runningTime - uselessTime;

		//Proper deletion of used dynamic memory.
		delete[] dummyArr;
		delete[] ref;
		//delete[] A;

		initialTime = 0;
		finalTime = 0;
		runningTime = 0;
		uselessTime = 0;

		//We write in the file the size of the array and the time it took to sort it.
		out << size << " " << finalTime << " " << std::endl;

		if (dotCounter % FREQUENCY_FOR_PROGRESS == 0)
		{
			std::cout << "Wrote " << dotCounter << " dots" << std::endl;
		}
	}
	
	out.close();

	return 0;
}

//Generates a random number with a very low probability of having the upper bound as a result.
//The srand must be initialized in the main() function that calls it.
int generateRandomNumber(int upperBound)
{
	return (int) (((double) rand() / RAND_MAX) * upperBound);
}

//Creates a list with a random size and with random numbers, if desired.
//We can tell to this function if we want some numbers to be swapped, in order to nearly sort the list.
int createList(int*& arr, bool random, bool nearlySorted, int maxSize)
{
	int size = generateRandomNumber(maxSize);
	arr = new int[size];

	for (int i = 0; i < size; ++i)
	{
		if (random)
			arr[i] = generateRandomNumber(RAND_MAX);
		else
			arr[i] = i;
	}
	if (nearlySorted)
	{
		for (int i = 0; i < (size / 50); ++i)
		{
			Swap(generateRandomNumber(size-1), generateRandomNumber(size-1), arr);
		}
	}

	return size;
}

//Necessary to simulate a call, in order to substract it to the total time.
int Nothing()
{
	return 0;
}

That error generally means that at some point your program wrote to a location outside the array's allocated memory. You see the error at the delete statement because the VS debugger gives these warnings at program exit.

Check your array access carefully for any out of bounds writing.

That error generally means that at some point your program wrote to a location outside the array's allocated memory. You see the error at the delete statement because the VS debugger gives these warnings at program exit.

Check your array access carefully for any out of bounds writing.

You were right. I checked the values of the array after the sort and I found a weird value (-3 billion ...). I used the provided heapsort in a wrong way.

Thanks for the help!

This question has already been answered. Start a new discussion instead.