Sorting
Q11.
The worst case running times of Insertion sort, Mergesort and Quicksort, respectively, are:Q12.
Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?Q13.
If one uses straight two-way merge sort algorithm to sort the following elements in ascending order:20, 47, 15, 8, 9, 4, 40, 30, 12, 17then the order of these elements after second pass of the algorithm is:Q14.
Consider the following sorting algorithms.I. QuicksortII. HeapsortIII> MergesortWhich of them perform in least time in the worst case?Q15.
Let P be a quick sort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?Q18.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Following algorithm(s) can be used to sort n in the range [1\ldots n^3] in O(n) timeQ19.
The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?Q20.
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n ( \geq2) numbers? In the recurrence equations given in the options below, c is a constant.