Counting sort is often used as a subroutine in which other sorting algorithm?
Quick Sort
Radix Sort
Heap Sort
Merge Sort
Which aspect of Radix Sort's implementation significantly impacts its overall performance, particularly for large datasets?
Initial order of elements in the input array
Number of passes required to sort all digits
Data structure used to store and access buckets
Choice of sorting algorithm for individual digits
What is the space complexity of Merge Sort?
O(log n)
O(n log n)
O(1)
O(n)
Bucket Sort can be considered a stable sorting algorithm under which condition?
The underlying sorting algorithm used within each bucket is stable.
The input data is already sorted.
The number of buckets is equal to the number of elements.
Bucket Sort is inherently stable regardless of the input or implementation.
What is a potential limitation of Heap Sort compared to some other efficient sorting algorithms?
It is less efficient when the input data is already nearly sorted.
It requires the entire dataset to be in memory.
Its average-case time complexity is worse than some other algorithms.
It is not well-suited for sorting linked lists.
Which of the following describes the space complexity of counting sort?
O(n + k), where k is the range of input values
How does the choice of pivot affect the performance of Quick Sort?
A poorly chosen pivot can lead to the worst-case time complexity of O(n^2)
Using the first element as the pivot is generally the most efficient approach
Selecting a random pivot always guarantees the best performance
The choice of pivot has no impact on the performance of Quick Sort
Why is binary search a preferred algorithm for searching in sorted arrays compared to linear search?
Binary search uses less memory than linear search.
Binary search is easier to implement and understand than linear search.
Binary search has a time complexity of O(log n), which is significantly faster than linear search's O(n) complexity for large datasets.
Binary search works correctly even on unsorted arrays, while linear search does not.
What makes Hoare's partitioning scheme generally preferred over Lomuto's in Quick Sort implementations?
Lomuto's scheme is not suitable for arrays with duplicate elements
Hoare's scheme performs fewer swaps on average, leading to better performance
Hoare's scheme is more intuitive and easier to implement
Lomuto's scheme always selects the last element as the pivot, leading to worse performance
Is Heap Sort a stable sorting algorithm?
Yes
No