Programming Project 1

Due: Monday, February 17, in class. Write a program to perform Shakersort on a file of integers. Shakersort operates similarly to Bubblesort, only it makes passes over the data in alternating directions. For example, if the contents of the file have been read into an array with the following configuration:

   4   7   9   5   3   7   8   4   3   2   1   9

Shakersort first makes a pass to the right (from cell zero to cell eleven), comparing adjacent cells' values and swapping them if the left cell's contents is greater that that of the right cell. Here are the results:

   4   7   5   3   7   8   4   3   2   1   9   9

Then Shakersort makes a second pass to the left (from cell ten to cell zero), comparing adjacent cells' values and swapping them under the same conditions. Here are the results:

   1   4   7   5   3   7   8   4   3   2   9   9

Make the third (and every odd numbered pass) from the left to the right and the fourth (and every even numbered pass) from the right to the left, until the array is sorted. Make each pass one shorter than the pass before to account for the integer that has found its final placement. Stop just as soon as the algorithm has ascertained that the list is sorted. This describes the basic project. For full credit, please add these refinements:

• Count the number of comparisons that the Shakersort executes for each set of data. Output and clearly label this integer.
• Determine if Shakersort performs better than the Bubblesort in our book. Copy this sort and use it to sort the same data that Shakersort uses. Output and clearly label this integer.
• Place a getch( ) at the conclusion of each function that prints data.
• Use the data that we supply for lists of sizes 100, 1000 and 10000. The data files are named 100.dat, 1000.dat, and 10000.dat in the folder I:\CSC122\Public\PP1Data.
• Your main should be organized this way:

  void main( )
  {  for (int i=0; i<3; i++)
     {  readData( ... );
        printData( ... );
        shakersort( ... );
        printData( ... );
        readData( ... );
        printData( ... );
        bubblesort( ... );
        printData( ... );
        displayStatisticalResults( ... );
     }
  }