OBJECTIVE:

Write a program to rearrange a given 'r * c' (r - rows, c - columns) matrix as follows: - each row is sorted in non-decreasing order - each column is sorted in non-decreasing order

PROCESSING:

You will perform the required sorted output of the matrix by two methods:

Method 1: Take all the 'r*c' elements in an array, sort it, then output row-wise (column-wise will also work!) as a 'r*c' matrix.

Method 2: Sort each row separately one-by-one. Then, sort each column separately one-by-one. Output this matrix.

Sorting Method: Use QuickSort.

Your program must have the following functions clearly identified and implemented:

1. The Comparison functions (three functions) - to compare an element to another element: - EQ(a, b) : if (a == b) return true, else return false. - LT(a, b) : if (a < b) return true, else return false. - GT(a, b) : if (a > b) return true, else return false. Note that other operators (!=, >=, <=) can be computed by combining the NOT operator with the above three. Each of the above three functions must increment a [global] counter 'comparison_count' (this will be needed for output). Obviously, one of your goals is to minimize the total number of element comparisons. Absolutely no element comparisons outside these functions.

2. The Assignment function: - ASSIGN(a, b): assigns a = b, or, a <- b. This function must increment a [global] counter 'assignment_count' (this will be needed for output). Note that a swap can be done by calling the assignment function three times. Obviously, one of your goals is to minimize the total number of element assignments. Absolutely no element assignments outside this function.

3. The PARTITION function. The partitioning must be done In-Place. For element comparisons and element assignments, you must use the above functions. Integer comparisons (like i < n), assignments (like i = 0), or arithmetic (like i++), need not be counted and can be done directly. In addition, the Partition method written by you must make exactly: ( - 1) (i.e., (right - left) in the variables used in lecture notes) element comparisons per call, for the actual partitioning. Comparisons and Assignments you make for choosing a better pivot (like median of 3 elements) are extra (note that they should also be counted by 'comparison_count' and 'assignment_count').

The program should output the sorted matrix and output the total number of element comparisons and element assignments taken for each of the methods.

INPUT:

You can assume the elements will be of type 'double'. Read the input matrix from a file named "input.txt". This file will have the matrix elements separated ONLY by "space" and "end of line (newline)" characters. The first line will have the number of rows and columns (separated by space). Thereafter, each line will contain the elements of a row (separated by space). You can assume each element value will be between 0.00 and 999.99 (rounded to two decimal places, so that you can format the output correctly). For example:

5 7 14 51.3 17 28.77 31 1 2 2 2 2 2 2.0 2 2 8 5 0.00 2 1 18.32 19 1 200.36 0 4 5.21 6.6 7 9 8 7 6.6 0.0 4 3

Test your program with matrix of size ~ 100-by-100.

No other characters will be present in the file. Note that your program must NOT take command line inputs.

OUTPUT(S):

Your program will generate 2 output files:

_1.txt: output the matrix for method 1 (keep same format as the input) output the total number of comparisons and assignments taken _2.txt: output the matrix for method 2 (keep same format as the input) output the total number of comparisons and assignments taken

For example, mine will be sadasis_1.txt and sadasis_2.txt.

Note that the output should be properly formatted like a matrix for easy readability.

Note that the input matrix shown above is NOT well formatted.

REPORT:

Write a report for the following in a file _report.txt. A simple text file (or word document) is good enough.

Write your observations on which method yields better (lesser) count. Compare them both theoretically (ORDER of growth) and practically (the count(s) you get based on your testing).

Also, does Method 2 always give a correct output (i.e., satisfies the objective given above)? If it does, then try to prove it. Otherwise, try to provide a simple example where it doesn't work.

the program must be written in c/c++