Q2Design and Analysis of Algorithms

Quick Sort, engineered by Tony Hoare in 1959, is fundamentally the most deployed, highly aggressive, and practical comparison-based sorting algorithm in modern computer science (forming the backbone of standard libraries in C, C++, and Java). Like Merge Sort, it rigidly utilizes the Divide and Conquer architectural paradigm. However, it operates in the exact mathematical reverse. While Merge Sort does all its heavy lifting during the bottom-up "Merge" phase, Quick Sort executes all its massive mathematical processing during the top-down "Divide" phase (known as Partitioning). Furthermore, it is an "In-Place" algorithm, meaning it aggressively modifies the original array directly, completely annihilating the massive $O(n)$ RAM overhead required by Merge Sort buffers.

The Algorithmic Execution and Partitioning Engine

The absolute core of Quick Sort is the highly complex Partitioning function. Its singular objective is to select a specific element and violently move it to its exact, mathematically correct final position in the array.

• 1. Pivot Selection: The algorithm selects a single element from the array to act as the "Pivot." (This can be the first element, the last element, a random element, or the median-of-three. The choice of pivot mathematically dictates the entire speed of the algorithm).
• 2. The Violent Partitioning (Lomuto or Hoare Scheme): Two pointers aggressively scan the array from opposite ends. The algorithm violently swaps elements to ensure a strict mathematical condition is met: EVERY single element physically located to the left of the Pivot must be mathematically less than or equal to the Pivot, and EVERY single element physically located to the right must be strictly greater than the Pivot.
• 3. The Recursive Divide: Once the Pivot is locked into its absolute final physical position, the array is shattered into two independent sub-arrays (the left side and the right side). The algorithm recursively calls itself on these two sub-arrays.

Concrete Computational Example

Let us sort the array: [10, 80, 30, 90, 40, 50, 70] (Choosing the last element, 70, as the Pivot).

• Initial State: Pivot = 70. The scanning pointer aggressively checks elements from left to right against 70.
• 10 < 70 (Keep left). 80 > 70 (Must go right). 30 < 70 (Keep left). 90 > 70 (Must go right). 40 < 70 (Keep left). 50 < 70 (Keep left).
• The Swaps: The algorithm physically swaps the large elements with the small elements to enforce the partition rule. The array transforms into: [10, 30, 40, 50, 70, 90, 80].
• Result: The Pivot (70) is now locked perfectly in the middle. The left sub-array [10, 30, 40, 50] and right sub-array [90, 80] are now fiercely independent and will be recursively Quick Sorted.

Rigorous Time Complexity and The Worst-Case Catastrophe

Quick Sort's mathematical execution time is completely dependent on how evenly the Pivot shatters the array.

• Best and Average Case: If the chosen Pivot consistently happens to be the exact mathematical median of the array, the array is shattered into two perfectly equal halves every single time. The recurrence relation is $T(n)=2T(n/2)+O(n)$, yielding a highly optimized, blisteringly fast time complexity of $\Theta (n\log n)$.
• The Worst-Case Degradation: If the array is already perfectly sorted (or reverse sorted) and the algorithm naively picks the last element as the Pivot, the Pivot will always be the largest element. The array will fail to split in half. It will violently shatter into one sub-array of size $n-1$ and another of size $0$. The recurrence collapses to $T(n)=T(n-1)+O(n)$. This causes a catastrophic, algorithmic meltdown, resulting in a devastating Time Complexity of $O(n^2)$, functioning no better than a primitive Bubble Sort.