Sorting Interview Questions Part 3

41.Sorting is not useful for
a. report generation
b. minimizing the storage needed
c. making searching easier and efficient
d. responding to queries easily
Ans. b


42. Choose the correct statements
a. Internal sorting is used if the number of items to be sorted is very large
b. External sorting is used if the number of items to be sorted is very large
c. External sorting does not need auxiliary storage
d. Internal sorting need auxiliary storage
Ans. b


43. A sorting technique that guarantees that records with the same primary key occurs in the same order in the sorted list as in the original unsorted list is said to be
a. stable b. consistent c. external d. linear
Ans. a


44.The running time of an algorithm is given by
T(n) = T(n-1) + T(n-2) – T(n-3),if n>3
= n,otherwise.
The order is
a. n b. log n c. n^n d. n^2
Ans. a
Let us find what is T(4) and T(5)
T(4) = T(3) + T(2) – T(1) = 3+2-1=4
T(5) = T(4)+ T(3) –(2) = 4+3-2=5
By induction it can be proved that T(n) = n.Hence order is n.


45.The order of an algorithm that finds whether a given Boolean function of ‘n’ variables,produces a 1 is
a. constant b. linear c. logarithmic d. exponential
Ans. d
In the worst case it has to be check all the 2^n possible input combinations,which is exponential .


46.You want to check whether a given set of items is sorted or not.Which of the following sorting methods will be the most efficient if it is already in sorted order?
a. Bubble sort b. Selection sort c. Insertion sort d.Merge sort
Ans. c


47. The average number of comparisons performed by the merge sort algorithm,in merging two sorted lists of length 2 is
a. 8/3 b. 8/5 c. 11/7 d.11/6
Ans. a
Merge sort combines 2 given sorted lists into one sorted list.For this problem let the final sorted order be a,b,c and d.The 2 lists(of length 2 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,average number of comparisons will be (2+3+3)/3=8/3.


48.Which of the following sorting methods will be the best if the number of swappings done is the only measure of efficiency?
a. bubble sort b. selection sort c. insertion sort d.quick sort
Ans. b


49.You are asked to sort 15 numbers randomly.You should prefer
a. bubble sort b. quick sort c. merge sort d. heap sort
Ans. a


50. As part of the maintenance work,you are entrusted with the work of rearranging the library books in a shelf in proper order,at the end of each day.The ideal choice will be
a. bubble sort b. insertion sort c. selection sort d. heap sort
Ans. b


51. Which of the following algorithms exhibits the unnatural behavior that,minimum number of comparisons are neede if the list to be sorted is in the reverse order and maximum number of comparisons are neede if they are already in order.
a. heap sort b. radix sort c. binary insertion sort d. there can’t be any such sorting method.
Ans. c


52.Which of the following sorting methods sorts a given set of items that is already in order or in reverse order with equal speed?
a. Heap sort b. Quick sort c. Insertion sort d. selection sort
Ans. b


53. A machine needs a minimum of 100 sec to sort 1000 names by quick sort.The minimum time needed to sort 100 names will be approx
a. 50.2 sec b. 6.7 sec c.72.7 sec d. 11.2 sec
Ans. b
In the best case quick sort algorithm makes nlogn comparisons.so,1000 * log(1000) = 9000 comparisons,which takes 100s.To sort 100 names a minimum of 100 * log(100)=600 comparisons are needed.This takes 100*600/9000 = 6.7 sec


54.A machine took 200 sec to sort 200 names,using bubble sort.In 800 sec,it can approximately sort
a. 400 names b. 800 names c. 750 names d. 850 names
Ans. a
For sorting 200 anmes bubble sort makes 200 * 199/2 = 19900 comparisons.So,the time needed for 1 comparison is 200 sec approx.In 800 sec it can make 80,000 comparisons.We have to find n,such that n(n-1)/2=80,000.solving n is approx 400.


55.The correct order of arrangement of the names Bradman,Lamb,May,Boon,Border,Underwood and Boycott,so that the quicksort algorithm makes the least number of comparisons is
a. Bradman,Border,Boon,Boycott,May,Lamb,Underwood
b. Bradman,Border,Boycott,Boon,May,Underwood,Lamb
c. Underwood,Border,Boon,Boycott,May,Lamb,Bradman
d. Bradman,May,Lamb,Border,Boon,Boycott,Underwood
Ans. a and b
Let the first element be the pivot element always.The best way is the one that splits the list into two equal parts each time.This is possible if the pivot elemnt is the median.Consider the given set of names or the equivalent set 1,2,3,4,5,6,7.4 is the median and hence should be the pivot element.Since the first element is the pivot element,4 should be the first element.so after the first pass,4 will be put in the correct place and we are left with 2 sublists 1,2,3 and 5,6,7.Since 2 is the median of 1,2,3 the list should be rearranged as 2,1,3 or 2,3,1.For similar reasons 5,6,7 should be rearranged as 6,5,7 or 6,7,5.Hence the answer.

56. Which of the following is/are correct in connection with sorting methods?
(a) Bubble sort uses sorting by an insertion technique to sort a file of numbers.
(b) Quick sort uses sorting by an exchange technique to sort a file of numbers.
(c) Shell sort uses sorting by an exchange technique to sort a file of numbers.
(d) Heap sort does not use sorting by an exchange technique to sort a file of numbers.
Ans. b


{2,8,13,6,7,27,18}
57)the maximum heap is created using the above set of integers, what would be the value at the 6th
position of the heap?
(a) 2 (b) 8 (c) 6
(d) 13 (e) 7
Ans. b

58.If one uses the quick sort algorithm to sort the following integers, how many pivot values are
required? You may assume that the pivot element is always selected as the last element of the respective
sub arrays. {50,22,11,78,16,95,7,75,51,41}.

(a) 7 (b) 8 (c) 4
(d) 6 (e) 5
Ans. d

59.If one uses the quick sort algorithm to sort the following set of integers how many pivot values are required?You may assume that the pivot element is always selected as the first element of the respective
sub arrays. {50,22,11,78,16,95,7,75,51,41}.

(a) 7 (b) 8 (c) 4
(d) 6 (e) 5
Ans. e

60.If one uses the bubble sort algorithm in ascending order ,in which of the following pairs will the data values not interchange during the first pass? {20,60,50,37,16,92,70,35}.
(a) 20,60 (b) 60,50 (c) 60,37
(d) 50,37 (e) 60,16
Ans. a