UPPCL AE 2018:46

Question

Which one of the following algorithms cannot sort $n$ numbers in $O(n)$ comparisons?

• A. Counting sort
• B. Radix sort
• C. Heap sort
• D. Bucket sort

Answer 1

hope this will help.

and I think quicksort is also not stable, please correct.

Comments

selection sort is not stable

Answer 2

Correct Answer : C

Sorting algorithms can be broadly classified based on whether they are comparison-based or non-comparison-based.

1. Comparison-Based Sorting Algorithms

These algorithms must compare elements to determine their order. The best possible time complexity for comparison-based sorting is O(nlog⁡n).
Heap Sort is a comparison-based sorting algorithm with a worst-case time complexity of O(nlog⁡n), so it cannot sort numbers in O(n)comparisons.

2. Non-Comparison-Based Sorting Algorithms

These algorithms do not rely on element-wise comparisons and can achieve linear time complexity O(n) under certain conditions:

• Counting Sort: O(n+k), works efficiently when the range of values k is not too large.
• Radix Sort: O(nk), where k is the number of digits in the largest number.
• Bucket Sort: O(n) on average when input is uniformly distributed.