Link to home
Start Free TrialLog in
Avatar of Aapkaahmad
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);
  }
Avatar of ozo
ozo
Flag of United States of America image

You're missing the final }
Avatar of chaos_hooi
chaos_hooi

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.
Avatar of Aapkaahmad

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.
ASKER CERTIFIED SOLUTION
Avatar of chaos_hooi
chaos_hooi

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial

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! ^_^