Sorting
Q11.
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 approximatelyQ12.
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?Q16.
Let P be a quicksort program to sort numbers in ascending order. Let t_{1} and t_{2} be the time taken by the program for the inputs \left[1 \ 2 \ 3 \ 4\right] and \left[5 \ 4 \ 3 \ 2 \ 1\right], respectively. Which of the following holds?Q17.
In a permutation a_1.....a_n of n distinct integers, an inversion is a pair (a_i, a_j) such that i \lt j and a_i \gt a_j. What would be the worst case time complexity of the insertion Sort algorithm, if the inputs are restricted to permutations of 1....n with at most n inversions?Q18.
If we use Radix Sort to sort n integers in the range \left (n^{k/2}, n^k \right ), for some k>0 which is independent of n, the time taken would be?Q20.
Choose the correct alternatives (More than one may be correct).The complexity of comparision based sorting algorithms is: