What is a key characteristic of in-place partitioning within the context of Quick Sort?
The partitioning process is performed entirely within the original array, without requiring the allocation of substantial additional memory proportional to the input size.
In-place partitioning is only applicable when the input array is already sorted in reverse order.
The partitioning step always selects the first element of the subarray as the pivot.
The algorithm sorts the array by recursively dividing it into smaller subarrays and then merging them back together.
What is the space complexity of Merge Sort?
O(n log n)
O(log n)
O(n)
O(1)
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 reduces the likelihood of selecting a very small or very large element as the pivot, thereby decreasing the chances of worst-case scenarios.
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.
Why is Quick Sort often preferred over Merge Sort in practice, despite having the same average-case time complexity?
Quick Sort is easier to parallelize and implement on multi-core processors
Quick Sort is an in-place sorting algorithm, while Merge Sort requires additional space for merging
Quick Sort has a lower constant factor in its time complexity, making it faster for smaller datasets
Quick Sort is more memory-efficient due to its recursive nature
Which of the following best describes the heap property in a binary heap used for Heap Sort?
Each node is smaller than or equal to its children
Each node is greater than or equal to its children
The heap is always a complete binary tree
The left and right subtrees are sorted
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(1) in both average and worst cases
O(n) in both average and worst cases
O(n) in the average case and O(log n) in the worst case
How does the choice of pivot affect the performance of Quick Sort?
The choice of pivot has no impact on the performance of Quick Sort
A poorly chosen pivot can lead to the worst-case time complexity of O(n^2)
Selecting a random pivot always guarantees the best performance
Using the first element as the pivot is generally the most efficient approach
Bucket Sort can be considered a stable sorting algorithm under which condition?
The input data is already sorted.
Bucket Sort is inherently stable regardless of the input or implementation.
The number of buckets is equal to the number of elements.
The underlying sorting algorithm used within each bucket is stable.
Which of the following describes the space complexity of counting sort?
O(n + k), where k is the range of input values
What is the worst-case time complexity of Heap Sort?
O(n^2)