write three sorting algorithms ( merge , insertion , quick) separately in each cpp file with a .h file . Call it in the main.cpp.

The instruction for main is as follows,

1. In main.cpp, the function main should have return type int and take two parameters argc and argv, in that order. The following example illustrates some basics to get you started. #include #include int main(int argc, char *argv[]){ printf("argc=%d ", argc); for (int i=0; i #include int main(int argc, char *argv[]){ FILE *fp1, *fp2; int n, v1, v2, v3; float x; double y; if (argc < 3){ printf("Usage: %s input_file output_file ", argv[0]); exit (1); } fp1 = fopen(argv[1], "r"); if (fp1 == NULL) { fprintf(stderr, "Error: cannot open file %s ", argv[1]); exit (1); } fp2 = fopen(argv[2], "w"); if (fp2 == NULL) { fprintf(stderr, "Error: cannot open file %s ", argv[2]); exit (1); } v1=fscanf(fp1, "%d", &n); v2=fscanf(fp1, "%f", &x); v3=fscanf(fp1, "%lf", &y); fprintf(fp2, "v1=%d, v2=%d, v3=%d ", v1, v2, v3); fprintf(fp2, "n=%d, n=%4d ", n, n); fprintf(fp2, "x=%f, x=%8.3f ", x, x); fprintf(fp2, "y=%lf, y=%8.3lf ", y, y); fclose(fp1); fclose(fp2); return 0; }

3. Your project should dynamically allocate memory as needed, and free the memory when it is no longer needed. The following example may be helpful to you. #include #include int main(int argc, char *argv[]){ FILE *fp; int i, n, *A; fp = fopen("INPUT.txt", "r"); if (fp == NULL) { fprintf(stderr, "Error: cannot open file INPUT.txt "); exit (1); } fscanf(fp, "%d", &n); A = (int *) malloc(n*sizeof(int)); if (A == NULL) { fprintf(stderr, "Error: cannot allocate memory "); exit (1); } for (i=0; i

4. a valid execution for the program should be in the following format read from the command line .

./PJ1 alg flag ( /PJ1 tells the system to search for the executable file PJ1 in the current directory, alg should be either InsertionSort, MergeSort, QuickSort indicating which sorting algorithm to use, and flag {0, 1} indicates whether each EWC (element-wise comparison) made in the sorting process should be printed out (print EWC if and only if flag = 1). Your program should check whether the execution is valid. If the execution is not valid, your program should print out the following error message and stop.

5. Now we assume that your program has successfully opened the file INPUT.txt for reading. For the test cases, the file INPUT.txt will all have the correct format, as described in the following. The file INPUT.txt contains n + 3 integers, for some positive integer n (where n may vary from one test case to another). Two consecutive integers are separated by one or more white spaces, where a white space is one of the following three characters: ' ' (i.e., space), '\t' (i.e., tab), ' ' (i.e., newline). If you are not familiar with this kind of input, you can assume (with a very small penalty) that the n + 3 integers are on the first n + 3 lines of the file, with one integer per line. You can quickly get going, and come back to revisit this issue if you have time. The meaning of the n + 3 integers in INPUT.txt and the corresponding actions of your program are as follows. The first integer is either 0 or 1. It is the value of printResult. If printResult = 1, your program will print out (on a new line) the content of array A after it is sorted, at the end of the program. The format of this line should be as follows. It starts the line with string "A:", followed by the n values of array A, with exactly one space (' ') between tokens. If printResult = 0, your program does not perform the above printing. The second integer is either 0 or 1. It is the value of printArray. If printArray = 1, your program will print out (on a new line) the content of array A each time after it is overwritten

6. Now your program will call the desired sorting algorithm to sort array A. The desired sorting algorithm is determined by the value of alg, which is read in from the command line. The function main will pass the following information to the corresponding function for sorting: A, p, r flag printArray For all three sorting algorithms, you should have p = 1 and r = n when main calls the sorting function. To make QuickSort unambiguous, the statement exchange A[i] and A[j] should be implemented by: temp = A[i] A[i] = A[j] A[j] = temp and the statement exchange A[i+1] and A[r] should be implemented by: temp = A[i+1] A[i+1] = A[r] A[r] = temp

If flag = 1, the sorting algorithm prints out each EWC (on a new line). The format of the EWC should be identical to the EWC in the algorithm, with exactly one space between the element, the comparison operator, and the question mark. If printArray = 1, the sorting algorithm prints out the portion of the array being sorted (on a new line) each time the array is overwritten. The format of this printing should have the form: A[p:r]: A[p] A[p+1] ... A[r], where the portion in red should be replaced by their corresponding values. The sorting function should also pass to its caller (main) the number of element-wise comparisons made in the sorting process.

7 outputting the result

After calling the desired sorting function, main should print out the number of element-wise com- parisons made in the sorting process, the following format. Number of EWCs: count_EWC with count EWC replaced by the number of element-wise comparisons made in the sorting process. If printResult = 1, main should also print out the content of the sorted array, on a new line. The line should start with the string "A[1:n] after sorting:", followed by the n elements of the sorted array, with exactly one space between two consecutive elements, and between : and the first element of sorted A. Here n has to be replaced by its value. If printResult = 0, main does not perform the above printing. Finally, main should release the memory dynamically allocated.

8. For instance

the input.txt would look like

0 0 4 4 3 2 1

/PJ1 InsertionSort 0 The output will be Number of EWCs: 6

if the input.txt was

1 1 4 4 3 2 1

./PJ1 InsertionSort 1

The output will be EWC: 4 > 3? A[1:4]: 4 4 2 1 A[1:4]: 3 4 2 1 EWC: 4 > 2? A[1:4]: 3 4 4 1 EWC: 3 > 2? A[1:4]: 3 3 4 1 A[1:4]: 2 3 4 1 EWC: 4 > 1? A[1:4]: 2 3 4 4 EWC: 3 > 1? A[1:4]: 2 3 3 4 EWC: 2 > 1?

A[1:4]: 2 2 3 4 A[1:4]: 1 2 3 4 A[1:4] after sorting: 1 2 3 4 Number of EWCs: 6