Aapkaahmad
asked on
Heap Sort Program in C++ that reads from file into array
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);
}
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);
}
You're missing the final }
I test your program and it sort perfectly using VC++. I just need to add the final } like Ozo said and include the stdlib.h for VC++ to get it to produce executable file.
ASKER
Thanks guys and I agree that the program does work (I had just forgotton to paste the last } when I submitted my question) but I want it to go into a .dat file and pull numbers out, sort them using heap algorithm and then output the sorted array into another .dat file. This is the output that I am currently getting:
syntax:
> heapsort <file1>
or
> heapsort <file1> <file2>
where, <file1> = input file of unordered numbers
and, <file2> = output sorted file
Press any key to continue
I am not sure what kind of environment you compile your program in, but you need to go to COMMAND PROMPT to be able to run this program. I am not sure whether VC++ (never use it much) has an easier way.
Anyway, first, you have to find the EXE file that it generated. If you are using VC++, it should have the same name, as your project with a .exe extension. If you are using unix system, it's the runnable file that you generated. If your runable file is heapsort.exe, open your command, go to that directory where the exe file with its input file (unsorted number, input.dat) is at:
heapsort input.dat output.dat
OR
heapsort.exe input.dat output.dat
NOTE:
input.dat contains your unsorted number.
output.dat will be your result file.
Anyway, first, you have to find the EXE file that it generated. If you are using VC++, it should have the same name, as your project with a .exe extension. If you are using unix system, it's the runnable file that you generated. If your runable file is heapsort.exe, open your command, go to that directory where the exe file with its input file (unsorted number, input.dat) is at:
heapsort input.dat output.dat
OR
heapsort.exe input.dat output.dat
NOTE:
input.dat contains your unsorted number.
output.dat will be your result file.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Good job! That worked out perfectly (for both of us). Enjoy your points!
Ahmad.Noordin
Technical Specialist/Programmer - ADP Benefits Inc.
Lead Interface Designer - www.commoncorner.com
Thanks! ^_^