What is the purpose of the partitioning step in the Quick Sort algorithm?
To find the median element of the array
To divide the array into two subarrays such that all elements in the left subarray are less than or equal to the pivot and all elements in the right subarray are greater than the pivot
To merge two sorted subarrays into a single sorted array
To sort the entire array in ascending order
What is the primary advantage of using counting sort over comparison-based sorting algorithms like merge sort or quick sort?
Counting sort can achieve a time complexity better than O(n log n) in certain scenarios.
Counting sort is a stable sorting algorithm by default.
Counting sort is an in-place sorting algorithm.
Counting sort works efficiently even for large datasets with a wide range of values.
How does the choice of pivot affect the performance of Quick Sort?
Selecting a random pivot always guarantees the best performance
The choice of pivot has no impact on the performance of Quick Sort
Using the first element as the pivot is generally the most efficient approach
A poorly chosen pivot can lead to the worst-case time complexity of O(n^2)
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 only used if the points are uniformly distributed in the plane; otherwise, a different approach is required.
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 not directly relevant to finding the closest pair of points; it can be solved more efficiently using hashing techniques.
What is the space complexity of Merge Sort?
O(log n)
O(n log n)
O(1)
O(n)
What is the primary purpose of topological sorting in the context of graph algorithms?
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 find the shortest path between any two nodes in a weighted graph.
To determine if a graph contains any cycles.
Which of the following best describes the heap property in a binary heap used for Heap Sort?
The heap is always a complete binary tree
The left and right subtrees are sorted
Each node is smaller than or equal to its children
Each node is greater than or equal to its children
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 worst-case time complexity of Heap Sort?
O(n^2)
What makes Hoare's partitioning scheme generally preferred over Lomuto's in Quick Sort implementations?
Hoare's scheme performs fewer swaps on average, leading to better performance
Lomuto's scheme is not suitable for arrays with duplicate elements
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