Solved
Heap Sort Program in C++ that reads from file into array
Posted on 2003-03-09
Hello fellow IT-ians?
I am currently attempting to write a c++ HEAP SORT program that reads integers from a file (ex: input.dat) up to a 1000 numbers and sorts them using the heap algorithm. It can output the sorted heap onto the screen or into another file (maybe: output.dat)
Below is what I have till now, but you don't have to use this program or format. The integers have to be read from a file, they cannot be generated randomly. I am offering 250 points since I need this very urgently! I hope someone can help me (and soon). Thanks!
/* FILE: heapSort.cpp author: Roberto Thomas
* This program reads a file of n unsorted integers and sorts them.
* The integers are first put into a static array,
* whose dimension is at most MAX_INTEGERS.
* Then, the array is made to satisfy the heap property.
* Finally, the biggest integer is iteratively extracted from the
* heap and put in the right place.
*/
#include <fstream.h>
#include <iostream.h>
const long int MAX_INTEGERS = 1000;
void Maximize(double*, const long int&, const long int&);
void MakeHeap(double*, const long int&);
void MaxSort(double*, const long int&);
main(int argc, char** argv) {
if (argc < 2 || argc > 3) {
cerr << "syntax:" << endl
<< " > heapsort <file1>" << endl
<< "or" << endl
<< " > heapsort <file1> <file2>" << endl
<< "where, <file1> = input file of unordered numbers" << endl
<< "and, <file2> = output sorted file" << endl;
exit(1);
}
ifstream in;
in.open(argv[1]);
if (!in.good()) {
cerr << "err: file " << argv[1] << " does not exist" << endl;
exit(1);
}
double A[MAX_INTEGERS+1];
long int n = 0;
do {
in >> A[++n];
if (n > MAX_INTEGERS) {
cerr << "err: file " << argv[1] << " contains more than "
<< MAX_INTEGERS << " integers." << endl;
exit(1);
}
} while (!in.eof());
in.close();
MakeHeap(A, n);
MaxSort(A, n);
if (argc == 2) for(long int i = 1; i <= n; i++) cout << A[i] << endl;
else {
ofstream out;
out.open(argv[2]);
if (!out.good()) {
cerr << "err: could not open file " << argv[2] << endl;
exit(1);
}
for(long int i = 1; i <= n; i++) out << A[i] << endl;
out.close();
}
}
inline void Maximize (double* A, const long int& i, const long int& j) {
long int root = i; bool done = false;
double value = A [i];
while ( 2*root <= j && ! done ) {
long int posMax = 2 * root;
if (posMax < j)
if (A [posMax+1] > A [posMax]) posMax++;
if (A [posMax] > value) {
A [ root ] = A [ posMax ];
root = posMax;
}
else done = true;
}
A [root] = value;
}
inline void MakeHeap (double* A, const long int& n) { // enforces the heap property
for(long int i = (n / 2); i >= 1; i--) Maximize(A, i, n);
}
void MaxSort (double* A, const long int& n) { // sorting from heap
long int i = n;
while (i > 1) {
double swap = A [1];
A [1] = A [i];
A [i] = swap;
i = i-1;
Maximize (A, 1, i);
}