What is the primary advantage of using a binary heap in Heap Sort?
Maintaining a sorted order during element extraction
Constant time insertion of elements
Efficient searching of elements
Low memory overhead compared to other heap structures
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)
The choice of pivot has no impact on the performance of Quick Sort
Selecting a random pivot always guarantees the best performance
Using the first element as the pivot is generally the most efficient approach
What is a key characteristic of in-place partitioning within the context of Quick Sort?
In-place partitioning is only applicable when the input array is already sorted in reverse order.
The algorithm sorts the array by recursively dividing it into smaller subarrays and then merging them back together.
The partitioning process is performed entirely within the original array, without requiring the allocation of substantial additional memory proportional to the input size.
The partitioning step always selects the first element of the subarray as the pivot.
In which scenario is Bucket Sort likely to perform poorly?
Data is already sorted in reverse order
Data is heavily skewed towards one end of the range
Data is uniformly distributed within a known range
Data consists of a small number of unique elements
What is the primary purpose of topological sorting in the context of graph algorithms?
To find the shortest path between any two nodes in a weighted graph.
To find the minimum spanning tree of a graph, connecting all nodes with the minimum total edge weight.
To arrange the nodes of a directed acyclic graph (DAG) in a linear order such that for every directed edge (u, v), node u comes before node v in the ordering.
To determine if a graph contains any cycles.
How does the space complexity of Heap Sort compare to other comparison-based sorting algorithms?
Heap Sort has a lower space complexity
Heap Sort typically has the same space complexity
Heap Sort has a higher space complexity
Heap Sort's space complexity depends on the input data
Which of the following best describes the role of the base case in a recursive implementation of Quick Sort?
To handle the comparison and swapping of elements during the sorting process
To select the pivot element for each recursive call
To define the condition when the array is fully sorted and the recursion should stop
To partition the array around a chosen pivot element
Is Heap Sort a stable sorting algorithm?
Yes
No
Why is Quick Sort often preferred over Merge Sort in practice, despite having the same average-case time complexity?
Quick Sort has a lower constant factor in its time complexity, making it faster for smaller datasets
Quick Sort is easier to parallelize and implement on multi-core processors
Quick Sort is more memory-efficient due to its recursive nature
Quick Sort is an in-place sorting algorithm, while Merge Sort requires additional space for merging
In counting sort, what does the count array store?
The cumulative sum of frequencies of elements less than or equal to each element in the input array.
The frequency of each distinct element in the input array.
The sorted elements of the input array.
The indices of elements in the input array.