Understanding Quick Sort: A Divide-and-Conquer Improvement Over Bubble Sort

Quick Sort Overview

Quick sort is an improvement over bubble sort that offers the best average performance among simple sorting algorithms.

Divide‑and‑Conquer Principle

The algorithm follows the divide‑and‑conquer method: it breaks the original problem into smaller sub‑problems that resemble the original, solves each recursively, and then combines the solutions to obtain the final sorted array.

Basic Idea

Given an unsorted segment R[low, high], a pivot element is chosen. Elements are compared with the pivot from both ends of the segment, moving pointers inward until all elements left of the pivot are smaller and all elements right are larger. This partitions the array into two sub‑segments, each of which is processed recursively until the entire array is sorted.

Time Complexity

The average time complexity of quick sort is O(n log n). In the worst case—such as when the smallest or largest element is repeatedly chosen as the pivot—the complexity degrades to O(n²).

Intuitive “Hole‑Filling” Analogy

The author likens quick sort to “digging a hole.” After selecting a pivot, the pivot’s position is temporarily emptied (the “hole”). A pointer starts from the right end, scanning leftward until it finds an element smaller than the pivot, which is placed into the hole. The vacated position becomes the new hole, and the process repeats from the opposite side. When the two pointers meet, the original pivot is placed into the final hole, guaranteeing that all elements left are smaller and all right are larger. The algorithm then recurses on the left and right sub‑segments.

Key Implementation Point

Once a pivot’s final position is determined, it remains fixed. The algorithm repeatedly finds the correct position for each new pivot through recursion, and the collection of these fixed positions yields the fully sorted array.