Which of the following algorithm(s) can be used to sort n integers in range [1…..n3] in O(n) time?
a) Heap sort b) Quick sort c) Merge sort d) Radix sort
The lower bound on the number of comparisons performed by comparison-based sorting algorithm is
a) Ω (1) b) Ω (n) c) Ω (nlogn) d) Ω (n2)
Time complexity to sort elements of binary search tree is
a) O(n) b) O(nlogn) c) O(n2) d) O(n2logn)
Which of the following sorting algorithm has the running time that is least dependant on the initial ordering of the input?
a) Insertion sort b) Quick sort c) Merge sort d) Selection sort
The radix sort does not work correctly if each individual digit is sorted using
a) Insertion sort b) Counting sort c) Selection sort d) Bubble sort
Which of the following sorting algorithm is in-place
a) Counting sort b) Radix sort c) Bucket sort d) None
The running time of radix sort on an array of n integers in the range [0……..n5 -1] when using base n representation is
a) θ (n) b) θ (nlogn) c) θ (n2) d) None
The running time of radix sort on an array of n integers in the range [0……..n5 -1] when using base 10 representation is
a) θ (n) b) θ (nlogn) c) θ (n2) d) none
Counting sort performs …………. Numbers of comparisons between input elements.
a) 0 b) n c) nlogn d) n2
Which of the following sorting algorithms is/are stable
a) Counting sort b) Bucket sort c) Radix sort d) All of the above
Which of the following algorithms has lowest worst case time complexity?
a) Insertion sort b) Selection sort c) Quick sort d) Heap sort
Given a number of elements in the range [0….n3]. Which of the following sorting algorithms can sort them in O(n) time?
a) Counting sort b) Bucket sort c) Radix sort d) Quick sort
Time complexity of bubble sort in best case is
a) θ (n) b) θ (nlogn) c) θ (n2) d) θ (n(logn) 2)
Consider the situation in which assignment operation is very costly. Which of the following sorting algorithm should be performed so that the number of assignment operations is minimized in general?
a) Insertion sort b) Selection sort c) Heap sort d) None
Which of the following algorithm pays the least attention to the ordering of the elements in the input list?
a) Insertion sort b) Selection sort c) Quick sort d) None
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