Three Partition Methods for QuickSort

Three Partition Methods for QuickSort

Problem Description
In the quicksort algorithm, partitioning is the core step. Its goal is to rearrange an array based on a chosen pivot element, such that all elements smaller than the pivot are to its left, and all elements greater than the pivot are to its right. Different partitioning methods affect the algorithm's performance and code implementation. This task requires mastering and implementing three classic partitioning methods: the Lomuto partition scheme, the Hoare partition scheme, and the three-way partition scheme.

Solution Process

  1. Understanding the Goal of Partitioning
    Given an array arr and its left and right boundaries left and right, select a pivot element pivot. After the partition operation, the array should satisfy:

    • All elements in arr[left...p-1] are <= pivot (for Lomuto and Hoare) or < pivot (for the strict left segment in three-way partition).
    • All elements in arr[p+1...right] are >= pivot (for Lomuto and Hoare) or > pivot (for the strict right segment in three-way partition).
    • The pivot element pivot itself is at its final correct position p (for Lomuto and Hoare) or within the middle segment (for three-way partition).

  2. Method One: Lomuto Partition Scheme
    This is the most intuitive and easiest-to-understand partitioning method.

    • Step-by-Step Details:

      1. Choose Pivot: Typically, select the rightmost element arr[right] as the pivot.
      2. Initialize Pointer: Set a pointer i initialized to left - 1. All elements at i and to its left represent the "processed and less than or equal to pivot" section.
      3. Traverse the Array: Use another pointer j to traverse from left to right - 1 (since right is the pivot).
      4. Compare and Swap: For each arr[j]:
        • If arr[j] <= pivot, this element should belong to the "less than or equal to pivot" region. We expand this region by one: first execute i = i + 1, then swap arr[i] and arr[j].
        • If arr[j] > pivot, do nothing, and let j continue moving forward.
      5. Place the Pivot: After the traversal, i points to the last element of the "less than or equal to pivot" region. At this point, i+1 is the correct position for the pivot. We swap arr[i+1] and arr[right] (the pivot).
      6. Return Pivot Position: Return i+1 as the final position of the pivot after this partition.

    • Code Example (Python):

      def lomuto_partition(arr, left, right):
    pivot = arr[right]  # Choose rightmost element as pivot
    i = left - 1        # Right boundary of <= region

    for j in range(left, right): # j traverses from left to right-1
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i] # Swap small element to <= region
    # Place pivot in correct position
    arr[i + 1], arr[right] = arr[right], arr[i + 1]
    return i + 1  # Return final pivot position

    • Characteristics: The code is concise, but when all elements are equal, it results in the worst-case O(n²) because each partition is extremely unbalanced (one part is n-1, the other is 0).

  3. Method Two: Hoare Partition Scheme
    This is the original method proposed by Tony Hoare, the inventor of quicksort. It is generally more efficient than Lomuto's method and involves fewer swaps.

    • Step-by-Step Details:

      1. Choose Pivot: Typically, select the leftmost element arr[left] as the pivot.
      2. Initialize Pointers: Set two pointers, i initialized to left - 1 and j initialized to right + 1.
      3. Scan Towards Each Other:
        • Move i from left to right until an element >= pivot is found.
        • Move j from right to left until an element <= pivot is found.
        • If at this point i < j, swap arr[i] and arr[j]. Because arr[i] (a "large" element) is incorrectly on the left, and arr[j] (a "small" element) is incorrectly on the right; swapping them moves towards correctness.
      4. Termination Condition: Repeat step 3 until i >= j. At this point, j is the partition boundary.
      5. Return Boundary: Return j. Note that the pivot element is not necessarily at position j, but it is guaranteed that arr[left...j] <= pivot and arr[j+1...right] >= pivot.

    • Code Example (Python):

      def hoare_partition(arr, left, right):
    pivot = arr[left]  # Choose leftmost element as pivot
    i = left - 1
    j = right + 1

    while True:
        # Note: Move pointer first, then compare
        i += 1
        while arr[i] < pivot: # Find first >= pivot
            i += 1

        j -= 1
        while arr[j] > pivot: # Find first <= pivot
            j -= 1

        if i >= j:
            return j # Return partition boundary j

        arr[i], arr[j] = arr[j], arr[i]

    • Characteristics: More efficient, but slightly more complex to understand. Note that during recursive calls, the intervals should be divided into [left, j] and [j+1, right].

  4. Method Three: Three-Way Partition Scheme
    This is the optimal method for handling arrays containing many duplicate elements, potentially optimizing complexity close to O(n).

    • Step-by-Step Details:

      1. Choose Pivot: Similarly, select a pivot (e.g., arr[left]).
      2. Initialize Pointers: Set three pointers:
        • lt (less than): All elements at and to the left of lt are strictly less than pivot. Initialized to left - 1.
        • i (current): Index of the element currently being checked. Initialized to left.
        • gt (greater than): All elements at and to the right of gt are strictly greater than pivot. Initialized to right + 1.
      3. Traverse and Classify: While i < gt, loop:
        • If arr[i] < pivot: It belongs to the "small" region. Swap arr[i] with the element at position lt+1, then lt++ and i++. Because lt+1 might be the first element of the equal region; after swapping, the equal element moves back, and the small element moves forward.
        • If arr[i] == pivot: It is already in the correct position (middle segment), simply i++.
        • If arr[i] > pivot: It belongs to the "large" region. Swap arr[i] with the element at position gt-1, then gt--. Note, do not increment i here because the element swapped from gt-1 hasn't been checked yet.
      4. Partition Result: After the loop ends, the array is divided into three segments:
        • [left, lt]: Elements strictly less than pivot.
        • [lt+1, gt-1]: Elements equal to pivot.
        • [gt, right]: Elements strictly greater than pivot.
      5. Recursion: Only need to recursively sort the strictly less than and strictly greater than segments; the middle segment equal to the pivot is already sorted.

    • Code Example (Python):

      def three_way_partition(arr, left, right):
    if left >= right:
        return
    pivot = arr[left]
    lt = left - 1
    i = left
    gt = right + 1

    while i < gt:
        if arr[i] < pivot:
            lt += 1
            arr[lt], arr[i] = arr[i], arr[lt]
            i += 1
        elif arr[i] == pivot:
            i += 1
        else: # arr[i] > pivot
            gt -= 1
            arr[gt], arr[i] = arr[i], arr[gt]
    # Recursively sort the less-than and greater-than regions
    # quick_sort_3way(arr, left, lt)
    # quick_sort_3way(arr, gt, right)
    return lt, gt # Return the two boundaries

    • Characteristics: Effectively handles duplicate elements and is one of the preferred quicksort optimizations in practical engineering (e.g., used in Java's Arrays.sort()).

Summary

  • Lomuto Scheme: Easy to understand and implement, often the first choice in teaching, but slightly less efficient.
  • Hoare Scheme: The original quicksort method, fewer swaps, higher efficiency.
  • Three-Way Partition: Best performance for arrays with many duplicate elements, avoiding performance degradation due to duplicates. In practical applications (e.g., Java's standard library), three-way partition is a common choice.