Problem Statement
Explain Quick Sort algorithm. How does partitioning work and how can you optimize pivot selection?
Explanation
Quick Sort is a highly efficient divide-and-conquer sorting algorithm that works by selecting a pivot element and partitioning the array around it. It is widely used due to its excellent average-case performance and in-place sorting capability.
The algorithm works as follows. First, choose a pivot element from the array using various strategies. Second, partition the array so that all elements smaller than the pivot come before it and all elements greater come after it. This puts the pivot in its final sorted position. Third, recursively apply Quick Sort to the subarrays before and after the pivot. The base case is when a subarray has one or zero elements.
The partitioning operation is the key to Quick Sort. Using the Lomuto partition scheme, we maintain an index i that tracks the boundary between smaller and larger elements. We iterate through the array with index j. If the current element is smaller than the pivot, we increment i and swap elements at i and j. This moves smaller elements to the left. Finally, we swap the pivot to its correct position at index i plus 1. Time complexity of partitioning is O of n as we examine each element once.
The Hoare partition scheme is an alternative that uses two pointers moving from both ends. Start with pointers at both ends. Move the left pointer right until finding an element greater than or equal to pivot. Move the right pointer left until finding an element less than or equal to pivot. Swap the elements at these pointers. Continue until pointers cross. This scheme makes fewer swaps on average than Lomuto.
Time complexity analysis shows that in the best and average cases, the pivot divides the array into roughly equal halves, creating log n levels of recursion with O of n work at each level, giving O of n log n total. In the worst case with poor pivot selection, each partition has size n minus 1 and 0, creating n levels with O of n work each, giving O of n squared. Space complexity is O of log n for the recursion stack in average case, O of n in worst case.
Pivot selection strategies significantly impact performance. Choosing the first or last element is simple but leads to worst case on sorted or reverse sorted arrays. Random pivot selection provides good average performance and avoids worst case on specific inputs. Median-of-three selects the median of first, middle, and last elements, providing good balance while being deterministic. Some implementations use median-of-five or even deterministic median-finding algorithms for guaranteed good pivots.
Advantages of Quick Sort include O of n log n average case with low constant factors making it faster than Merge Sort in practice. It sorts in-place requiring only O of log n extra space for recursion. It has good cache performance due to localized memory access. It is easy to implement and widely used in standard libraries.
Disadvantages include O of n squared worst case which can occur with poor pivot selection, though randomization makes this extremely unlikely. It is not stable as equal elements may be reordered. Recursive implementation can cause stack overflow for large arrays if not optimized with tail recursion or switching to Heap Sort for deep recursion.