Description

Department of Computer Science and Engineering
Third Semester B. Tech.(CSE)
CS2092D Programming Laboratory Assignment #3
Policies for Submission and Evaluation:
• Ensure that your programs will compile and execute without errors in the Linux platform.
• Detection of ANY malpractice related to the lab course can lead to awarding an F grade in the course.
Naming Conventions for Submission
• Submit a single ZIP (.zip) file (do not submit in any other archived formats like .rar, .tar, .gz). The name of this file must be
ASSG < NUMBER > < ROLLNO > < FIRST − NAME > .zip
(For example: ASSG1 BxxyyyyCS LAXMAN.zip). DO NOT add any other files (like temporary files, input files, etc.) except your source code, into the zip archive.
• The source codes must be named as
ASSG < No. > < ROLLNO > < FIRST − NAME > < PROGRAM − No. > .c
(For example: ASSG1 BxxyyyyCS LAXMAN 1.c). If you do not conform to the above naming conventions, your submission might not be recognized by our automated tools, and hence will lead to a score of 0 marks for the submission. So, make sure that you follow the naming conventions.
Standard of Conduct
General Instructions
• Programs should be written in C language and compiled using C compiler in Linux platform. Submit the solutions to questions 1 and 2 through the submission link in Eduserver.
The Sorting Problem can be formally stated in terms of the input/output relationship as follows:
Input: A sequence of n numbers ha1,a2,…,ani
Output: A permutation of the input sequence such that .
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