I'm trying to sort an array of numbers with heap sort, but it's not sorting the first number in the array.
Here is my code:
Code:
#include <iostream>
using namespace std;
int BuildMaxHeap(int array1[], int n);
int MaxHeapify(int array1[], int i, int n);
int Heapsort(int array1[], int n);
int main()
{
int array1[11] = {11, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9};
Heapsort(array1, 10);
for (int z = 0; z < 11 ; z++)
{
cout << array1[z] << " ";
}
cout << endl;
return 0;
}
int MaxHeapify(int array1[], int i, int n)
{
int c=0;
int l = i << 1; ++c;
int r = (i << 1) + 1; ++c;
int largest; ++c;
// Is left larger than i?
if (++c && (l <= n) && (array1[l] > array1[i]))
{
largest = l; ++c;
}
else
{
largest = i; ++c;
}
// Is right larger than largest?
if (++c && (r <= n) && (array1[r] > array1[largest]))
{
largest = r; ++c;
}
// Need swap??
if (++c && largest != i)
{
int temp = array1[i]; ++c;
array1[i] = array1[largest]; ++c;
array1[largest] = temp; ++c;
c += MaxHeapify(array1, largest, n); ++c;
}
return c;
}
int BuildMaxHeap(int array1[], int n)
{
int c=0;
for (int i = n / 2; ++c && i >= 1; i--)
{
c += MaxHeapify(array1, i, n); ++c;
}
return c;
}
int Heapsort(int array1[], int n)
{
int c=0;
BuildMaxHeap(array1, n); ++c;
for (int i = n; ++c && i >= 2; i--)
{
// exchange i with 1
int temp = array1[1]; ++c;
array1[1] = array1[i]; ++c;
array1[i] = temp; ++c;
c += MaxHeapify(array1, 1, i-1); ++c;
}
return c;
}
I'm pretty sure the reason is because the whole sorting algorithm is made for a 1 based array (where the first position is 1, not 0). I'm pretty sure it's an easy fix, but i've been trying for a long time and can't figure it out. If I made the first position in the array a dead spot, and shifted the values one spot, this would fix the problem, but i can't figure out how.
Also, for my real program, i read the numbers in from a file ( i created the above one so it could be copied and pasted to run. The real program requires a file, and needs to be run using the command prompt, so the solution to my problem could be slightly different in each case):
Code:
int main(int argc, char* argv[])
{
int *array1 = NULL;
int size;
//First value in the file is assigned to "size".
inFile >> size;
array1 = new int[size];
//FillArray
for (int i = 0; i < size; i++)
{
inFile >> array1[i];
}
//InsertionSort(array1, size);
//Quicksort (array1, 0, size-1);
Heapsort(array1, size-1);
//MergeSort(array1, 0, size-1);
//BubbleSort(array1, size);
//ShellSort(array1, size);
PrintArray(array1, size);
delete [] array1;
array1 = NULL;
cin.get();
return 0;
}
In this, i launch the program in the command prompt like:
and the file looks like (the first number is the number of values, and the rest are just random values):
Code:
10
1
6
4
8
2
4
9
8
4
2
All my other sorting algorithms work in this program except for the heap sort. Once again, i think it's because of the 0 based array problem.
Thanks.