Sorting
April 18, 2024Question 10667 – Sorting
April 18, 2024GATE 1992
|
Question 19
|
Following algorithm(s) can be used to sort n integers in the range [1…n3] in O(n) time
|
Heapsort
|
|
|
Quicksort
|
|
|
Mergesort
|
|
|
Radixsort
|
Question 19 Explanation:
As no comparison based sort can ever do any better than nlogn. So option (A), (B), (C) are eliminated. O(nlogn) is lower bound for comparison based sorting.
As Radix sort is not comparison based sort (it is counting sort), so can be done in linear time.
As Radix sort is not comparison based sort (it is counting sort), so can be done in linear time.
Correct Answer: D
Question 19 Explanation:
As no comparison based sort can ever do any better than nlogn. So option (A), (B), (C) are eliminated. O(nlogn) is lower bound for comparison based sorting.
As Radix sort is not comparison based sort (it is counting sort), so can be done in linear time.
As Radix sort is not comparison based sort (it is counting sort), so can be done in linear time.