Description
Programs should be written in C language and compiled using C compiler in Linux platform.
The Sorting Problem can be formally stated in terms of the input/output relationship as follows: Input: A sequence of n numbers (ai, a2, .. • , an)
Output: A permutation (di, a2, … , 4) of the input sequence such that di < d2 < • • • < 4.
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
