How does Kruskal's algorithm utilize sorting to find the minimum spanning tree of a graph?
It sorts the edges of the graph in increasing order of their weights and then iteratively adds edges to the growing minimum spanning tree while avoiding the formation of cycles.
It sorts the nodes of the graph based on their distances from a randomly chosen starting node.
Sorting is not used in Kruskal's algorithm; it's a greedy algorithm that makes locally optimal choices without the need for sorting.
It sorts the nodes of the graph in ascending order of their degrees (number of connected edges).
Which of the following is a common use case for Merge Sort?
Sorting a small array with less than 10 elements
Sorting a linked list
Finding the smallest element in an array
Sorting a nearly sorted array
How does the space complexity of Heap Sort compare to other comparison-based sorting algorithms?
Heap Sort has a lower space complexity
Heap Sort has a higher space complexity
Heap Sort typically has the same space complexity
Heap Sort's space complexity depends on the input data
What is a potential limitation of Heap Sort compared to some other efficient sorting algorithms?
Its average-case time complexity is worse than some other algorithms.
It requires the entire dataset to be in memory.
It is not well-suited for sorting linked lists.
It is less efficient when the input data is already nearly sorted.
How does tail recursion optimization benefit the implementation of Quick Sort?
It prevents stack overflow errors by converting recursion into iteration
It reduces the time complexity of the algorithm from O(n^2) to O(n log n)
It simplifies the implementation of the partitioning scheme
It improves the average-case performance of the algorithm but does not affect the worst case
How does Merge Sort handle the base case of a single-element subarray?
It considers a single-element array as inherently sorted.
It recursively divides the single-element array.
It performs a swap operation on the element.
It throws an error, as a single-element array cannot be sorted.
Counting sort is often used as a subroutine in which other sorting algorithm?
Radix Sort
Quick Sort
Merge Sort
Heap Sort
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 is consistently faster
Radix Sort has the same time complexity
Radix Sort can be faster under certain conditions
Radix Sort is always slower
What is the primary disadvantage of using Radix Sort compared to comparison-based sorting algorithms?
Limited applicability to specific data types
Inability to handle negative numbers effectively
Higher space complexity due to bucket usage
Significant performance degradation for nearly sorted data
Which of the following is a key advantage of Merge Sort?
Constant space complexity
Best-case time complexity of O(n)
Stable sorting
In-place sorting