MCQs on Sorting with answers
MCQs on Sorting with answers
1. Which of the following is not a stable sorting algorithm?a) Insertion sort
b) Selection sort
c) Bubble sort
d) Merge sort
View Answer / Hide Answer2. Which of the following is a stable sorting algorithm?a) Merge sort
b) Typical in-place quick sort
c) Heap sort
d) Selection sort
View Answer / Hide Answer3. Which of the following is not an in-place sorting algorithm?a) Selection sort
b) Heap sort
c) Quick sort
d) Merge sort
View Answer / Hide Answer4. Running merge sort on an array of size n which is already sorted isa) O(n)
b) O(nlogn)
c) O(n
2)
d) None
View Answer / Hide Answer5. The time complexity of a quick sort algorithm which makes use of median, found by an O(n) algorithm, as pivot element isa) O(n
2)
b) O(nlogn)
c) O(nloglogn)
d) O(n)
View Answer / Hide Answer6. Which of the following is not a noncomparison sort?a) Counting sort
b) Bucket sort
c) Radix sort
d) Shell sort
View Answer / Hide Answer7. The time complexity of heap sort in worst case isa) O(logn)
b) O(n)
c) O(nlogn)
d) O(n
2)
View Answer / Hide Answer8. 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
View Answer / Hide Answer9. 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
View Answer / Hide Answer10. 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
View Answer / Hide Answer11. Time complexity of bubble sort in best case isa) θ (n)
b) θ (nlogn)
c) θ (n
2)
d) θ (n(logn)
2)
View Answer / Hide Answer12. 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
View Answer / Hide Answer13. Which of the following algorithms has lowest worst case time complexity?a) Insertion sort
b) Selection sort
c) Quick sort
d) Heap sort
View Answer / Hide Answer14. Which of the following sorting algorithms is/are stablea) Counting sort
b) Bucket sort
c) Radix sort
d) All of the above
View Answer / Hide Answer15. Counting sort performs …………. Numbers of comparisons between input elements.a) 0
b) n
c) nlogn
d) n
2 View Answer / Hide Answer16. The running time of radix sort on an array of n integers in the range [0……..n5 -1] when using base 10 representation isa) θ (n)
b) θ (nlogn)
c) θ (n
2)
d) none
View Answer / Hide Answer17. The running time of radix sort on an array of n integers in the range [0……..n5 -1] when using base n representation isa) θ (n)
b) θ (nlogn)
c) θ (n
2)
d) None
View Answer / Hide Answer18. Which of the following sorting algorithm is in-placea) Counting sort
b) Radix sort
c) Bucket sort
d) None
View Answer / Hide Answer19. The radix sort does not work correctly if each individual digit is sorted usinga) Insertion sort
b) Counting sort
c) Selection sort
d) Bubble sort
View Answer / Hide Answer20. 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
View Answer / Hide Answer21. Time complexity to sort elements of binary search tree isa) O(n)
b) O(nlogn)
c) O(n
2)
d) O(n
2logn)
View Answer / Hide Answer22. The lower bound on the number of comparisons performed by comparison-based sorting algorithm is a) Ω (1)
b) Ω (n)
c) Ω (nlogn)
d) Ω (n
2)
View Answer / Hide Answer23. 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
View Answer / Hide Answer24. Which of the following algorithm design technique is used in the quick sort algorithm?a) Dynamic programming
b) Backtracking
c) Divide-and-conquer
d) Greedy method
View Answer / Hide Answer25. Merge sort usesa) Divide-and-conquer
b) Backtracking
c) Heuristic approach
d) Greedy approach
View Answer / Hide Answer26. For merging two sorted lists of size m and n into sorted list of size m+n, we require comparisons ofa) O(m)
b) O(n)
c) O(m+n)
d) O(logm + logn)
View Answer / Hide Answer27. A sorting technique is called stable if ita) Takes O(nlogn) times
b) Maintains the relative order of occurrence of non-distinct elements
c) Uses divide-and-conquer paradigm
d) Takes O(n) space
View Answer / Hide Answer28. In a heap with n elements with the smallest element at the root, the seventh smallest element can be found in timea) θ (nlogn)
b) θ (n)
c) θ (logn)
d) θ (1)
View Answer / Hide Answer29. 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) θ (n
2)
b) θ (nlogn)
c) θ (n
1.5)
d) θ (n)
View Answer / Hide Answer30. In a binary max heap containing n numbers, the smallest element can be found in timea) θ (n)
b) θ (logn)
c) θ (loglogn)
d) θ (1)
View Answer / Hide Answer
Discussion
- RE: MCQs on Sorting with answers -Saurav kumar (08/07/23)
- Bubble Sort time complexity is O(n^2) But options are incorrect.
- RE: MCQs on Sorting with answers -Aarav Pant (08/14/20)
- Thank for the mcqs with answers.
- In a heap with n elements with the smallest element at the root, the seventh smallest element can be found in time -Abhishek Kumar (09/16/18)
- Answer-O(1).
For k-1 times repeat the following :
Extract the root of the new min-heap using extract-min and insert the 2 children of the extracted root from the original heap into the new heap. Resulting heap will contain k elements and root of which will be our kth smallest in the original heap. This grows the new heap by one on every removal (remove one, add two), which means it will never hold more than K elements, and so the remove-one-add-two will take O(3*log(K)). After k iterations, it is O(3*k*logk) = O(k*logk).
In order to implement this, Nodes in the new heap should store indexes of their corresponding nodes in the original heap, rather than the node values themselves.
For 7 elements, it will take 7log7 = O(1) time as new heap will create only 7 elements. - RE: MCQs on Sorting with answers -Sushil Tiwari (03/17/17)
- Under the section of sorting question number 11 which is something like "Time complexity of bubble sort in best case is ?"
Answer for this question is O(n^2) not O(n) as your explanation says.You could verify the correction on Wikipedia or other standard references. - RE: MCQs on Sorting with answers -Tim (01/09/17)
- I think Q28 should have a more suitable answer as O(logn).
We got a "seventh smallest" as a constant, but we still have to adjust the heap in O(logn) time. - RE: MCQs on Sorting with answers -praffulla (08/14/16)
- Q28 should have answer as O(1).
