INSTRUCTIONS:

You are writing a program. It must compile, execute and produce the desired output in one of the CS department lab machines. Use C/C++ or Java. If you want to use any other language, you must get approval from Instructor. In some cases (especially, if you use a different language from the ones suggested), you *may* be asked to show that your program compiles, executes and produces the desired output, by scheduling a meeting time with the Grader/Instructor.

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.

SUBMISSION:

Submit your source file(s) and report (zip it first!) into Canvas (you absolutely must zip it), before class on due date. Note that the submission time is set in Canvas - it won't take submissions beyond the due date/time strictly. To be on the safe side - make sure your submission is in, at least an hour before actual due date/time.

POINTS (TENTATIVE):

Program Compiles, Runs, Correct Output, No major issues, for both methods: 25 points EQ, GT, LT, and ASSIGN methods correctly done: 10 points PARTITION makes (right-left) comparisons: 5 points Output is formatted correctly: 5 points Good/Correct Report: 5 points Bonus points for getting low comparison count: 5 points

INFO/FAQ (this list will be updated as new questions come up):

1. You may reuse the algorithm(s) provided in the lecture notes (modifications may be needed!).

2. You may compare your answers (i.e., count) with another student - to make sure you haven't made simple mistakes - but don't look at or copy someone's code.

3. Try to reduce the comparison and assignment count. Note that the algorithms given in class are inefficient. For example, in the algorithm (method 2) given in lecture notes, every time "j--" happens, we just made 2 comparisons - when we could do it with just 1. Think about this!

4. In any one submission - all required files must be included. If you submit your assignment more than once, then the latest submission will be graded. The earlier ones may be deleted without notice!

5. Check that your program compiles and runs in the CS Dept lab machines. This will save you time later.

6. Make sure you have proper backup of all your work. Please don't say - my dog ate my laptop, my hard drive crashed, etc.

7. Don't hard code the number of rows/cols. It should be read from the input file.

please can someone help me with this. Can you please do both the methods and help me with writing report.

program should be written in c++

could you tell me what else information should I provide