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;
}