CS2092D - Programming Laboratory -  Assignment 3 - Solved

QUESTIONS 
General Note: For the following programs, do not declare the array as a global variable. You may pass the arrays as function arguments by using the concept of pointers.
1. Write a program that uses the INSERTION-SORT algorithm for sorting a given sequence of integers present in an array A and prints the number of comparisons performed during sorting. Your program must contain the following functions.
•    INSERTION-SORT(A) - A function that takes as input an array A and sorts it using insertion sort.
•    PRINT(A) - A function that takes as input an array A and prints its contents in order, with a single space separating the elements. This function should only be called from the MAIN() function.
Input format:
•    The first line of the input contains an integer n E [0,104], the size of the array A.
•    The second line lists the n elements in A, as space-separated integers in the range [-1000, 1000]. Output Format:
•    The first line of the output contains the elements of A in non-decreasing sorted order, with a single space separating each element.
•    The second line of the output contains the number of comparisons performed (between the elements of A) during sorting.
Note:
The number of comparisons made can vary a little depending on the way Insertion Sort is implemented. As such, we will be considering the number of comparisons as per the Insertion Sort algorithm given in CLRS.
Sample Input 1:
10
23 76 89 3 8 0 789
Sample Output 1: 0 3 8 23 25 76 89 17    123 2789 25
123 789 2789
Sample Input 2:                
10
90 89 78 67 56 45    34    23    12    11
Sample Output 2:                
11 12 23 34 45 56    67    78    89    90
45                
 
2. Write a program that uses the MERGE-SORT algorithm for sorting a given input sequence of integers present in an array A and prints the number of comparisons performed during sorting. Your program must contain the following functions. (In what follows, the notation A[p..r] denotes the sub-array of A, contained within the pth and rth indices, both inclusive.)
•    A recursive function MERGE-SoRT(A, p, r) that takes as input an array A and sorts the elements in the sub-array A[p..r].
•    A function MERGE(A, p, q, r) that takes as input an array A in which the sub-arrays A[p..q] and A[q+1..r] are sorted. It then merges these sub-arrays such that the the sub-array A[p..r] is sorted.
•    PRINT(A) - A function that takes as input an array A and prints its contents in order, with a single space separating the elements. This function should only be called from the MAIN() function.
Input format:
•    The first line of the input contains an integer n E [0, 105], the size of the array A.
•    The second line lists the n elements in A, as space-separated integers in the range [-103,103]. Output Format:
•    The first line of the output contains the elements of A in sorted order, separated by space.
•    The second line of the output contains the number of comparisons performed during sorting. Notes:
•    The number of comparisons made can vary a little depending on the way Merge Sort is implemented. As such, we will be considering the number of comparisons as per the Merge Sort algorithm given in CLRS.
•    In particular, to split an array A[p..r] into two sub-arrays, the MERGE-SORT() function should compute an index q E [p, r] such that A[p..q] contains [n/21 elements, and A[q+1..r] contains Ln/2_1 elements).
Sample Input 1:
10
23 76 89 3 8 0 789
Samle Output 1:    123 2789        25
0 3 8 23 25 76 89    123    789 2789
34                
Sample Input 2:                
10                
90 89 78 67 56 45    34    23    12    11
Sample Output 2:                
11 12 23 34 45 56    67    78    89    90
34