CSC133 Introduction to CS Using C++
Lab 8

In this lab you will write a program that reads two files of sorted numbers and merges them to create a sorted output file which has all the numbers from both files. For example, given the following input files:

Your program should create the following output file:

10
15
20
25
30
40
65
80
100
110
120
150
175
180

Merging is the basis of an efficient sorting algorithm called Merge Sort. It is often used when sorting files that are too large to be read entirely into memory and sorted. Merging will produce a sorted output file only if the two input files are sorted.

Processing

When you compare a number from each file, you will find one of the numbers is less, and you will write that number to the output file. Suppose you decide to write the number from File 1. At this point, you should read another number from File 1. You should NOT read another number from File 2, because the current number from File 2 has not been written to the output file. And it cannot be written until it is compared to the next number from File 1.

When you get to end of file on one of the input files, there may still be data in the other input file. For example, suppose you reach end of file on File 2. There is at least number word from File 1 that must be written to the output file; this is the number that was last compared to a number from File 2. In addition, there may be more numbers left in File 2. Since File 1 is now empty, these numbers can be written to the output file without any comparisons.

Considering the preceding, your program should perform the following steps:

   open the input files and the output file
   read number1 from input file1
   read number2 from input file2
   while neither file reaches eof
      if number1 < number2
         write number1 to output file
         read number1 from input file 1
      else
         write number2 to output file
         read number2 from input file 2
   end of while loop

   if file1 has reached eof
      while not eof on file 2
         write number2
         read number2 from file 2
      end of while loop
   else
      while not eof on file 1
         write number1
         read number1 from file 1
      end of while loop

To write this program you will create the following functions:

• Function intro will print your name, course and section number, and the lab number.
• Function main will open the files, read and compare the numbers, and create the output file.

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

© Copyright Emmi Schatz 2004