CS2092D Assignment #3 Solution

QUESTIONS

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 ∈ [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 123 2789 25
Sample Output 1:
0 3 8 23 25 76 89 123 789 2789
17
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 ∈ [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 ∈ [p,r] such that A[p..q] contains dn/2e elements, and A[q+1..r] contains bn/2c elements).
Sample Input 1:
10
23 76 89 3 8 0 789 123 2789 25
Samle Output 1:
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