Counting sort is often used as a subroutine in which other sorting algorithm?
Quick Sort
Merge Sort
Radix Sort
Heap Sort
What is the space complexity of Quick Sort in the average and worst case scenarios?
O(1) in both average and worst cases
O(n) in the average case and O(log n) in the worst case
O(log n) in the average case and O(n) in the worst case
O(n) in both average and worst cases
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.
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 based on their distances from a randomly chosen starting node.
It sorts the nodes of the graph in ascending order of their degrees (number of connected edges).
In computational geometry, how is sorting used in finding the closest pair of points from a set of points in a 2D plane?
Sorting is not directly relevant to finding the closest pair of points; it can be solved more efficiently using hashing techniques.
The points are sorted randomly, and the distances between consecutive points are compared to find the closest pair.
The points are sorted based on their x-coordinates, and then a divide-and-conquer approach is used to efficiently compare distances between points in the sorted order.
Sorting is only used if the points are uniformly distributed in the plane; otherwise, a different approach is required.
What is the space complexity of Merge Sort?
O(log n)
O(1)
O(n)
O(n log n)
In counting sort, what does the count array store?
The sorted elements of the input array.
The indices of elements in the input array.
The frequency of each distinct element in the input array.
The cumulative sum of frequencies of elements less than or equal to each element in the input array.
What is the primary advantage of using counting sort over comparison-based sorting algorithms like merge sort or quick sort?
Counting sort works efficiently even for large datasets with a wide range of values.
Counting sort can achieve a time complexity better than O(n log n) in certain scenarios.
Counting sort is an in-place sorting algorithm.
Counting sort is a stable sorting algorithm by default.
What is the primary disadvantage of using Radix Sort compared to comparison-based sorting algorithms?
Inability to handle negative numbers effectively
Limited applicability to specific data types
Higher space complexity due to bucket usage
Significant performance degradation for nearly sorted data
What is the significance of lexicographic sorting in string processing?
It sorts strings based on the number of vowels they contain.
It sorts strings based on their lengths, from shortest to longest or vice versa.
It sorts strings based on their hash values, making it very efficient for comparing large strings.
It sorts strings in alphabetical order, considering the order of characters defined by the character encoding (e.g., ASCII or Unicode).
What is the worst-case time complexity of Merge Sort?
O(n^2)