Handwritten Quick Sort (Including Comparison of Three Partition Methods)

Problem Description
Required to manually implement the Quick Sort algorithm and understand the impact of different Partition strategies on performance. The core of Quick Sort is to divide the sequence to be sorted into two independent parts in one pass, where all elements in one part are smaller than the elements in the other part, and then recursively sort these two parts.

Solution Process

1. Algorithm Framework
Quick Sort adopts the divide-and-conquer approach, with the following steps:

1. Partition: Select a pivot value and rearrange the array so that all elements smaller than the pivot are placed on its left, and all elements larger than the pivot are placed on its right.
2. Recursion: Recursively apply Quick Sort to the left and right sub-arrays of the pivot.
3. Merge: Since the pivot is already in its final position after each partition, no merge operation is needed.

2. Basic Partition Method: Lomuto Partition

• Steps:
  1. Choose the rightmost element as the pivot (e.g., arr[high]).
  2. Initialize pointer i = low-1, used to mark the end of the sub-array smaller than the pivot.
  3. Traverse j from low to high-1:
     • If arr[j] <= pivot, then i++, swap arr[i] and arr[j].
  4. Place the pivot in its correct position: swap arr[i+1] and arr[high].
  5. Return the pivot's position i+1.
• Code Example:

  def lomuto_partition(arr, low, high):
      pivot = arr[high]  # Choose rightmost element as pivot
      i = low - 1        # Right boundary of region smaller than pivot
      for j in range(low, high):
          if arr[j] <= pivot:
              i += 1
              arr[i], arr[j] = arr[j], arr[i]
      arr[i+1], arr[high] = arr[high], arr[i+1]
      return i + 1
  

• Characteristics: Simple code, but performs swaps even when all elements are equal, leading to lower efficiency.

3. Optimized Partition Method: Hoare Partition

• Steps:
  1. Choose the middle element as the pivot (e.g., arr[(low+high)//2]).
  2. Initialize two pointers i = low-1, j = high+1.
  3. Loop:
     • Move i to the right until arr[i] >= pivot.
     • Move j to the left until arr[j] <= pivot.
     • If i >= j, return j as the partition point; otherwise, swap arr[i] and arr[j].
• Code Example:

  def hoare_partition(arr, low, high):
      pivot = arr[(low + high) // 2]  # Choose middle element
      i, j = low - 1, high + 1
      while True:
          i += 1
          while arr[i] < pivot:  # Find element on left >= pivot
              i += 1
          j -= 1
          while arr[j] > pivot:  # Find element on right <= pivot
              j -= 1
          if i >= j:
              return j
          arr[i], arr[j] = arr[j], arr[i]
  

• Characteristics: Fewer swaps, higher efficiency, but note that the recursion boundaries should be [low, j] and [j+1, high].

4. Optimization for Duplicate Elements: Three-Way Partition

• Applicable Scenario: When the array contains many duplicate elements, partition the array into three parts (less than, equal to, greater than the pivot).
• Steps:
  1. Initialize pointers lt = low, i = low, gt = high.
  2. Choose a pivot (e.g., arr[low]), traverse i from low to gt:
     • If arr[i] < pivot, swap arr[lt] and arr[i], lt++, i++.
     • If arr[i] > pivot, swap arr[gt] and arr[i], gt-- (i does not move at this point).
     • If arr[i] == pivot, i++.
  3. Recursively sort [low, lt-1] and [gt+1, high].
• Code Example:

  def three_way_partition(arr, low, high):
      pivot = arr[low]
      lt, i, gt = low, low, high
      while i <= gt:
          if arr[i] < pivot:
              arr[lt], arr[i] = arr[i], arr[lt]
              lt += 1
              i += 1
          elif arr[i] > pivot:
              arr[gt], arr[i] = arr[i], arr[gt]
              gt -= 1
          else:
              i += 1
      return lt, gt  # Return boundaries of the interval equal to pivot
  

5. Complete Quick Sort Implementation (Using Hoare Partition as an example)

def quicksort(arr, low, high):
    if low < high:
        pi = hoare_partition(arr, low, high)  # Get partition point
        quicksort(arr, low, pi)    # Recursively sort left part
        quicksort(arr, pi + 1, high)  # Recursively sort right part

6. Key Points Summary

• Stability: Quick Sort is an unstable sorting algorithm (swaps may disrupt order).
• Time Complexity:
  • Average Case: \(O(n \log n)\).
  • Worst Case (sorted array + fixed pivot selection): \(O(n^2)\), can be avoided by randomly choosing the pivot.
• Space Complexity: Average recursion stack depth is \(O(\log n)\), worst case \(O(n)\).
• Partition Method Selection:
  • Lomuto: Easy to understand, but has many swaps.
  • Hoare: Fewer swaps, higher efficiency.
  • Three-Way Partition: Suitable for scenarios with many duplicate elements, avoids recursion on duplicates.