Data Structures and Algorithms MCQ - Sorting and Searching

36 You want to check whether a given set of items is sorted. Which of the following sorting methods will be most efficient if it is already in sorted order?

37 The average number of comparisons performed by the merge sort algorithm, in merging two sorted liss of length 2 is

Merge-sort combines two given sorted lists into one sorted list. For this problem let the final sorted order be- 1, b, c, d. The two lists (of length two each) should fall into one of the following 3 categories. (i) a, b and c,d (ii) a, c and b, d (iii) a, d and b, c The number of comparisons needed in each case will be 2, 3, 3. So, the average number of comparisons will be (2=3+3)/3= 8/3 Here is a better way of doing; Let list L1 have the items a,c and L2 have the items b,d. The tree drawn below depicts the different possible cases. (a & b means a is compared with b. If a is smaller, the edge will be labeled a. The number within a circle, beside the leaf nodes, is the number of comparisons, needed to reach it.) From the tree, we find there are 6 possible ways, the total number of comparisons needed is 3+3+2+2+3+3=16. So, the average number of comparisons is 16/6= 8/3

38 Which of the following sorting methods will be the best if the number of swappings done, is the only measure of efficiency?

Because in the selection sort algorithm we randomly access data rather than a list in which we can easily swap data which we want to swap and it takes less time. So, the answer is 'B'

39 You are asked to sort 15 randomly generated numbers. You should prefer

40 As part of the maintenance work, you are entrusted with the work of rearranging the library books on a shelf in proper order, at the end of each day. The ideal choice will be