Quick Sort Interview Question Part 2

17. Which of the following statement(s) best describes the quicksort algorithm
(a)Partitioning the file into two subfiles, selecting some pivot value, sorting the two sub-files sequentially.
(b)Selecting some pivot value, partitioning the file into N sub-files and sorting independently, merging all sub-files into single file.
(c)Selecting some pivot value, partitioning the file into two sub-files, sorting the two sub-files independently in recursive way.
(d)Partitioning the file into two sub-files, sorting these two sub-files independently, then partitioning two sub-files into four sub-files, sorting these four sub-files independently. This process is repeating until entire file becomes sorted.
Ans:c


18. If one chooses the middle key as the pivot, what would be the Big-O value for the Best case of the Quick Sort Algorithm? (a) n*n (b) n (c) a constant (d) n log n
Ans:d


19. Which of the following is/are correct in connection with the time complexity of the quick sort algorithm in the worst case, best case and average case respectively? (a) n*n, n, nlog n (b) nlog n, nlog n, nlog n (c) n*n, nlog n, nlog n (d) n, n, nlog n
Ans:c
20. The basic quicksort algorithm is recursive and consists of four steps, but the following steps are in incorrect order.
(i) Pick any element v in S. This element is called pivot.
(ii) Return the result of Quicksort(L), followed by v, followed by quicksort(R)
(iii) Partition S – {v} (the remaining elements in S) into two disjoint groups: L={x S – {v} | x =< v} and R={x S – {v} | x >v }
(iv) If the number of elements in S is 0 or 1 then return.

Which of the following is the correct order of steps in the quicksort algorithm?
(a) (iv), (iii),(i),(ii)
(b) (i),(ii),(iii),(iv)
(c) (iv), (i),(iii),(ii)
(d) (i),(iii),(ii),(iv)
Ans:c


21. Which of the following activities is/are not relevant to the quick sort algorithm?
(a) Initially divide the entire file into N sub-files.
(b) Choose a pivot value and store it in a correct place.
(c) The sorting technique is sorting by exchange.
(d) The sorting technique is sorting by selection.
Ans:a,d
22. If the last element is chosen as the pivot at each iteration, the Quick-sort tree for
the sequence in question 1 will have height:
a)1
b) 2
c) 3
d)4
Ans:c


23. If Quick-sort were implemented so that the element at position n/2 is chosen as
the pivot, which of the following sequences would be the worst input?
a) 1 2 3 4 5 6 7
b) 2 3 4 1 5 6 7
c) 7 6 5 4 3 2 1
d) 5 6 7 1 2 3 4
e) 6 4 2 7 1 3 5
Ans:d

24. Given a large amount of highly random data which fits into the computers RAM,
the best choice for sorting would be:
a) Bubble-sort
b) Insertion-sort
c) Merge-sort
d) Quick-sort
Ans:d

25. In Quick sort , after the completion of every pass the pivot/key element moves to the ________ position. a.first b.second c.middle d.exact sorted position
Ans:d