Back to General and Gameplay Programming

My heap sort keeps on crashing (C++)

ISDCaptain01 · 2013-04-09T07:47:04

I made a heapsort today, but when I run it, I always get an error and my compiler aborts the program Well here is my walkdown algorithm: template <class DataType> //HeapWalkDown: Walks down an a node in array // (Array, Index of parent of the lowest node, Size of the array, comparison function) void HeapWalkDown( Array<DataType> &p_array, int p_index, int p_maxIndex, int (*p_compare)(DataType, DataType)) { //Keeps track of the current parent index int parent = p_index; //Keeps track of the current child index int child = p_index * 2; //Stores the data that is being walked down into a temporary variable DataType temp = p_array[parent]; //Starts a loop, loops through the tree until the child index is //greater then the tree size while(child <= p_maxIndex) { //If the left child is not the last node in the tree, then //find out which of the current node's children is the largest if(child < p_maxIndex) { //Compare the left and right child to see which one holds //the larger value // LEFT CHILD RIGHT CHILD if(p_compare(p_array[child], p_array[child + 1]) < 0) { //If the right child has the larger, then increment the child index //because the the index of the right child is always is one larger //then the left child child++; } } //Now the function knows which child it wants to move upward. It //Determines if the child node needs to move upward by comparing //it to the value in the temp variable if(p_compare(temp, p_array[child]) < 0) { //Moves the child upward into the parent index p_array[parent] = p_array[child]; // parent = child; child *= 2; } //If no swap is needed else { break; } } //The value in temp is placed into the correct index p_array[parent] = temp; } and heres the heapsort function: //Heapsort: Sorts an array into a heap, then turn the heap into a //sorted array template <class DataType> void Heapsort( Array<DataType> &p_array, int (*p_compare)(DataType, DataType)) { //Used to loop through the array int index; //Keeps track of the size of the array int maxIndex = p_array.Size(); //The index of the last node's parent int rightindex = maxIndex/2; //Turns the array into a heap by walking down everything to //its proper place for(index = rightindex; index > 0; index--) { //Walk everything down, turning the array into a heap HeapWalkDown(p_array, index, maxIndex, p_compare); } //Starts creating a sorted array from the newly formed heap while(maxIndex > 0) { //Swap the root with the last node in the tree Swap(p_array[0], p_array[maxIndex - 1]); //Decrease the size of the tree maxIndex--; //Walk Down the top index HeapWalkDown(p_array, 1, maxIndex, p_compare); } } //Swap: Swap a left and right variable around template <class DataType> void Swap( DataType& a, DataType& b ) { static DataType t; t = a; a = b; b = t; } Note they all are in one header file and here is my source file which demonstrates the sort #include <iostream> #include "Array.h" #include "Heapsort2.h" #include <stdlib.h> #include <time.h> using namespace std; //Comparison function int intcompare(int l, int r) { return l - r; } int comparereverseint(int l, int r) { return r - l; } int comparefloat(float l, float r) { if(l > r) return 1; if(l < r) return -1; return 0; } //Function automatically prints an array template <class DataType> void PrintArray(Array<DataType> p_array) { for(int i = 0; i < p_array.m_size; i++) { cout << p_array << ", "; } cout << endl << endl; } int main() { //Create two arrays Array<int> iarray(16); Array<float> farray(16); //Seed the random number generator srand(time(0)); //Fills the array with random values for(int index = 0; index < 16; index++) { iarray[index] = rand() % 256; farray[index] = (float)(rand() % 256) / 256.0f; } //Display the Unsorted arrays cout << "Unsorted Integer array: " << endl; PrintArray(iarray); cout << "Unsorted Float array: " << endl; PrintArray(farray); //Sort the arrays HeapSort(iarray, intcompare); HeapSort(farray, comparefloat); //Display the sorted arrays cout << "Sorted Integer array: " << endl; PrintArray(iarray); cout << "Sorted Float array: " << endl; PrintArray(farray); cin.get(); return 0; } any help would be appreciated

General and Gameplay Programming Programming

Started by ISDCaptain01 April 07, 2013 12:20 AM

11 comments, last by BitMaster 11 years ago

MrP

565

April 08, 2013 03:40 AM

You're passing your Array object to the PrintArray function by value rather than by reference. As a result the parameter is a copy of the passed in argument (and therefore its m_array member points to the same address), so when the destructor is invoked at the end of the function the memory pointed to by both instances is deleted.

ISDCaptain01

1,499

Author

April 09, 2013 03:35 AM

Wow, it finally worked. You guys were right, it was the PrintArray function not taking a reference to an array.

Once again, you guys are truly awesome. Thank you

My Portfolio:

http://aasimsgamelab.weebly.com

BitMaster

8,652

April 09, 2013 07:47 AM

Since your Array class does not implement proper copy semantics you should explicitly delete the copy constructor and assignment operator (in C++11) or set them private (before C++11) to prevent an accidental copy (which never works with that class).

Considering how far your Array class is behind std::vector (both regarding features and correctness in other aspects) I would also strongly suggest that you either make implementing a proper array class the whole point of the learning experience (not as simple as it sounds) or using std::vector.

On a more personal note, if I ever catch you "using namespace std;" at the top of a header I'm forced to use or work with, I will hunt you down.

My heap sort keeps on crashing (C++)

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

My heap sort keeps on crashing (C++)

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines