**Your cart is currently empty!**

$ 24.99

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

## Reviews

There are no reviews yet.