Quick Sort Algorithm

# CHAPTER 16

Quick Sort Algorithm #

1. Introduction #

2. Learning Objectives #

• Explain the logic of Pivot Selection and Partitioning.

• Trace the physical pointer swapping during In-Place sorting.

• Analyze why Quick Sort operates in $O(1)$ Auxiliary Space.

• Prove how terrible Pivot selection degrades performance to $O(N^2)$.

• Contrast the structural stability of Merge Sort vs Quick Sort.

3. The Execution Logic #

Phase 1: Choose a Pivot The algorithm randomly selects one single element from the array to act as the Pivot. (For simplicity, we often just pick the element at the far right Index [N-1]).

Phase 2: Partitioning (The Magic) The algorithm iterates through the array.

• If a number is smaller than the Pivot, it swaps it to the left side.

• If it is larger, it leaves it on the right side.

• Finally, it drops the Pivot directly into the exact middle gap between the small and large numbers!

Phase 3: Recursion The algorithm executes a recursive Call Stack dive on the unsorted left chunk, and the unsorted right chunk.

4. Visualizing the Partition #

Array: [10, 80, 30, 90, 40, 50, 70]
Pivot Chosen: 70

Partitioning Scan:
Is 10 < 70? Yes. Swap Left. -> [10, 80, 30, 90, 40, 50, 70]
Is 80 < 70? No. Ignore.
Is 30 < 70? Yes. Swap Left. -> [10, 30, 80, 90, 40, 50, 70]
...
Final Pivot Drop:
[10, 30, 40, 50] --> 70 <-- [90, 80]
*Notice: 70 is permanently sorted. The left/right chunks are NOT sorted yet.*

5. Implementation in Code #

// Java Example: Quick Sort
public class Sort {
    
    // The Partition Engine
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // Choosing the absolute last element as Pivot
        int i = (low - 1);     // Pointer for the smaller elements

        for (int j = low; j < high; j++) {
            // If current element is smaller than the pivot
            if (arr[j] <= pivot) {
                i++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // Scan complete. Swap the Pivot into its final resting gap (i + 1)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1; // Return the permanently sorted Pivot index
    }

    // The Recursive Controller
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Find the Pivot index
            int pi = partition(arr, low, high);

            // Recursively sort elements BEFORE the pivot
            quickSort(arr, low, pi - 1);
            // Recursively sort elements AFTER the pivot
            quickSort(arr, pi + 1, high);
        }
    }
}

6. Complexity Analysis: The Ultimate Gamble #

7. Senior Optimization: The "Median-of-Three" Pivot #

8. Stability Classification #

9. Real-World Applications #

• Embedded C/C++ Systems: If you are writing software for a microcontroller, a pacemaker, or a drone, RAM is violently restricted. You absolutely cannot afford Merge Sort's $O(N)$ Space overhead. Quick Sort is the undisputed king of embedded high-speed sorting.

10. Common Mistakes #

• Recursion Base Case Failure: If you forget if (low < high) in the controller function, the Recursion will attempt to partition an array of zero elements, instantly throwing a Stack Overflow Exception.

11. Exercises #

1. 1. Trace the Partition function step-by-step for the array [8, 2, 4, 7, 1, 3, 9, 6, 5]. Assuming 5 is the pivot, what does the array physically look like after the exact moment the Pivot is dropped into the middle?

1. 2. Why is Quick Sort practically useless for sorting Singly Linked Lists?

12. MCQs with Answers #

13. Interview Preparation #

• *Algorithmic Defense:* "An interviewer asks: If both Quick Sort and Merge Sort are Average-Case $O(N \log N)$, why is Quick Sort empirically faster in real-world server environments?" *(Answer: "Cache Locality!" Because Quick Sort operates strictly In-Place upon contiguous blocks of memory, the CPU can load the entire array block into the blazing-fast L1/L2 Hardware Cache, resulting in nanosecond hardware extraction speeds. Merge Sort's external auxiliary arrays force the CPU to constantly read/write to the much slower standard RAM!).*

14. FAQs #

15. Summary #

16. Next Chapter Recommendation #