In which scenario is Bucket Sort likely to perform poorly?
Data consists of a small number of unique elements
Data is uniformly distributed within a known range
Data is already sorted in reverse order
Data is heavily skewed towards one end of the range
Which of the following describes the space complexity of counting sort?
O(log n)
O(n + k), where k is the range of input values
O(n)
O(1)
How does the time complexity of Radix Sort compare to comparison-based sorting algorithms like Merge Sort and Quick Sort for integers with a wide range?
Radix Sort can be faster under certain conditions
Radix Sort is consistently faster
Radix Sort has the same time complexity
Radix Sort is always slower
What is a key limitation of counting sort?
It is only efficient for datasets with an even number of elements.
Its space complexity can be significant if the range of input values is large.
It cannot sort datasets containing duplicate values.
It is not suitable for sorting strings or objects.
Is Merge Sort an in-place sorting algorithm?
No
Yes
What is the primary disadvantage of using Radix Sort compared to comparison-based sorting algorithms?
Higher space complexity due to bucket usage
Limited applicability to specific data types
Inability to handle negative numbers effectively
Significant performance degradation for nearly sorted data
Which of the following is a common use case for Merge Sort?
Sorting a nearly sorted array
Sorting a linked list
Sorting a small array with less than 10 elements
Finding the smallest element in an array
What is the space complexity of Quick Sort in the average and worst case scenarios?
O(log n) in the average case and O(n) in the worst case
O(n) in the average case and O(log n) in the worst case
O(1) in both average and worst cases
O(n) in both average and worst cases
What is the primary motivation behind using randomized Quick Sort?
To make the sorting process more unpredictable and challenging for analysis.
To provide a probabilistic guarantee of achieving the average-case time complexity, even for potentially adversarial input sequences.
To simplify the implementation of the partitioning step compared to deterministic pivot selection methods.
To make the algorithm's running time completely independent of the input data.
How does using the median-of-three partitioning strategy in Quick Sort help optimize its performance?
It eliminates the need for recursive calls in the sorting process, making it significantly faster.
It has no impact on the performance of Quick Sort; it's simply an alternative partitioning approach.
It guarantees the selection of the median element as the pivot, always leading to perfectly balanced partitions.
It reduces the likelihood of selecting a very small or very large element as the pivot, thereby decreasing the chances of worst-case scenarios.