23. Quick Sort: The Pivot Strategy (Part 1)

Quick Sort is the most widely used sorting algorithm in practice. Like Merge Sort, it uses the Divide and Conquer paradigm.

Concept: Partitioning

The key to Quick Sort is the Partition operation. It relies on choosing a pivot element and rearranging the array such that:

1. All elements smaller than the pivot come before it.
2. All elements greater than the pivot come after it.

After partitioning, the pivot element is guaranteed to be in its final sorted position.

Quick Sort Steps

1. Choose Pivot: Select an element (often the last or a random element).
2. Partition: Reorder the array around the pivot.
3. Recurse: Recursively apply Quick Sort to the subarray of elements less than the pivot and the subarray of elements greater than the pivot.