If the given input array is sorted or nearly sorted, which of the following algorithm gives the best performance?
a) Insertion sort b) Selection sort c) Quick sort d) Merge sort
The time complexity of heap sort in worst case is
a) O(logn) b) O(n) c) O(nlogn) d) O(n2)
Which of the following is not a non-comparison sort?
a) Counting sort b) Bucket sort c) Radix sort d) Shell sort
What would be the worst case time complexity of the insertion sort algorithm, if the inputs are restricted to permutation of 1…..n with at most n inversion?
a) θ (n2) b) θ (nlogn) c) θ (n1.5) d) θ (n)
Running merge sort on an array of size n which is already sorted is
a) O(n) b) O(nlogn) c) O(n2) d) None
Which of the following is not an in-place sorting algorithm?
a) Selection sort b) Heap sort c) Quick sort d) Merge sort
Which of the following is a stable sorting algorithm?
a) Merge sort b) Typical in-place quick sort c) Heap sort d) Selection sort
Which of the following is not a stable sorting algorithm?
a) Insertion sort b) Selection sort c) Bubble sort d) Merge sort
In addition to the pancake sorting problem, there is the case of the burnt pancake problem in which we are dealing with pancakes (discs) that are burnt on one side only. In this case it is taken that the burnt side must always end up _______
a) Faced down b) Faced up c) It doesn’t matter d) Both sides are burnt
The given array is arr = {2,3,4,1,6}. What are the pivots that are returned as a result of subsequent partitioning?
a) 1 and 3 b) 3 and 1 c) 2 and 6 d) 6 and 2
What is the best case complexity of QuickSort?
a) O(nlogn) b) O(logn) c) O(n) d) O(n2)
For merging two sorted lists of size m and n into sorted list of size m+n, we require comparisons of
a) O(m) b) O(n) c) O(m+n) d) O(logm + logn)
What is the advantage of bubble sort over other sorting techniques?
a) It is faster b) Consumes less memory c) Detects whether the input is already sorted d) All of the mentioned
The best case for the recursion are sub problems of size _____.
a) 0 or 1 b) 2 or 3 c) 4 or 5 d) 6 or 7
_______ is a sorting algorithm based on the divide-and-conquer paradigm.
a) Shell sort b) Heap sort c) Merge-sort d) Quick sort
Merge sort has _______ running time
a) log n b) O(log n) c) n logn d) O(n log n)