?
Solved

Heap Sort Program in C++ that reads from file into array

Posted on 2003-03-09
7
Medium Priority
?
598 Views
Last Modified: 2007-12-19
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);
  }
0
Comment
Question by:Aapkaahmad
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 2
7 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 8101337
You're missing the final }
0
 
LVL 4

Expert Comment

by:chaos_hooi
ID: 8101645
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.
0
 

Author Comment

by:Aapkaahmad
ID: 8104979

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
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 4

Expert Comment

by:chaos_hooi
ID: 8107244
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.
0
 
LVL 4

Accepted Solution

by:
chaos_hooi earned 1000 total points
ID: 8107432
Okay, found out how you can input program arguments in VC++... you can go to Project --> Settings --> Debug --> type your program arguments in the [Program Arguments]...

For e.g.,

To output the result to output.dat...
input.dat output.dat

To output the result to the screen...
input.dat
0
 

Author Comment

by:Aapkaahmad
ID: 8108681

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
0
 
LVL 4

Expert Comment

by:chaos_hooi
ID: 8108747
Thanks! ^_^
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Navigation is an important part of web design from a usability perspective. But it is often a pain when it comes to a developer’s perspective. By navigation, it often means menuing. This is less theory and more practical of how to get a specific gro…
There is an easy way, in .NET, to centralize the treatment of all unexpected errors. First of all, instead of launching the application directly in a Form, you need first to write a Sub called Main, in a module. Then, set the Startup Object to th…
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
Suggested Courses

765 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question