SPRING 2006 Due Monday, 4/17 CS 321 Programming Assignment 7 This program concerns a new sorting algorithm known as Columnsort.1   Columnsort works as follows.  It begins with n = r*s values placed in an r x s matrix, where r mod s = 0 and At the end of the algorithm, the r x s matrix will be sorted if the values are read in column-major order. Columnsort involves 8 steps. 1. Sort the values in each column. 2. "Transpose" the matrix by reading s values at a time in column-major order and putting them back into the matrix in row-major order. 3. Sort the new columns. 4. Reverse step 2 – access in row-major order and insert in column-major order. 5. Sort the new columns. 6. Access the values in column-major order and shift the values down (and up to the top of the next column) by positions. You will need to create one additional column to accommodate this shift. Fill the first half of the first column (now empty) with the value and the bottom half of the new column with the value . 7. Sort the new columns. 8. Reverse the shift of step 6, that is, access the values in column-major order and shift them up by positions. The extra column will go away and the result will be values that, in column-major order, are sorted. Here is a simple example where n = 27. The original 27 values are: 14 3 21 24 8 26 19 10 2 25 1 12 23 13 4 17 15 20 9 27 7 16 18 5 22 11 6 These are inserted in column-major order (i.e., by columns) into an r x s matrix where r = 9, s = 3. Note that the conditions on n, r, and s are met. Original matrix After Step 1 After Step 2 After Step 3 After Step 4 After Step 5 After Step 6 After Step 7 After Step 8 In a separate program, create a file of 100,000 random integers (Lab7.txt). Set the maximum numeric value to 32,000, which will guarantee duplicate values, but that doesn't matter. The maximum value returned by the rand function is 32767, so you could actually never get a value above this anyway without some multiplication. More to the point, in order to avoid a stack overflow when you run your program, you will use the data type short int, which uses 2 bytes to store an integer, so the maximum value for type short int is also 32767. Read the file into a matrix (of type short int), sort it in increasing order using Columnsort, then write the sorted results to an output file called Results.txt. Instead of measuring work by counting comparisons, you will compute the actual wall clock time taken by the sorting algorithm. Since you are not counting operations, the array can just hold the integers from the file, no need to use Key objects. Use the Timer class in the back of the book to compute the wall clock time. Do not count the time needed to read the values from the data file into the matrix nor the time to output the sorted results back to a file. Before you write to the file, use a final check to be sure your values are indeed sorted, something like bool SortCheck(matrix[ ][ ]) //precondition: items have supposedly been sorted //postcondition: returns true if sorted, false if not Your program should output (to the screen) your choice of r and s values and the wall clock time to the nearest millisecond. Do your own implementation, because we'll be looking for who gets the fastest time.