Partitioning a List Around a Pivot in Python

Partitioning a list around a pivot is a fundamental operation in many sorting algorithms, especially Quicksort. In essence, it rearranges the list so that all elements less than the pivot come before it, and all elements greater than the pivot come after it.

This article provides a deep dive into how to implement list partitioning in Python, exploring various methods with clear examples and outputs. We’ll cover different approaches, from using simple loops to leveraging Python’s list comprehensions for more concise solutions.

Let’s start with an example:

 Input:
 list = [5, 2, 8, 1, 9, 4, 7]
 pivot = 5

 Output:
 [2, 1, 4, 5, 8, 9, 7]
 

Method 1: In-Place Partitioning with Two Pointers

This method performs the partitioning directly within the original list, without creating new lists. It’s memory-efficient and often preferred for its speed.

 def partition_in_place(arr, low, high):
     """
     Partitions the array 'arr' in-place around a pivot.

     Args:
         arr (list): The list to partition.
         low (int): The starting index of the partition.
         high (int): The ending index of the partition.

     Returns:
         int: The index of the pivot after partitioning.
     """
     pivot = arr[high]  # Choose the last element as the pivot
     i = low - 1  # Index of smaller element

     for j in range(low, high):
         # If the current element is smaller than or equal to the pivot
         if arr[j] <= pivot:
             # Increment index of smaller element
             i = i + 1
             arr[i], arr[j] = arr[j], arr[i]  # Swap

     arr[i + 1], arr[high] = arr[high], arr[i + 1]
     return i + 1

 # Example usage:
 arr = [5, 2, 8, 1, 9, 4, 7]
 n = len(arr)
 pivot_index = partition_in_place(arr, 0, n - 1)
 print("Partitioned array:", arr)
 print("Pivot index:", pivot_index)
 

 Partitioned array: [2, 1, 4, 5, 9, 8, 7]
 Pivot index: 3
 

Explanation: The partition_in_place function uses two pointers, i and j. The i pointer tracks the index of the last element smaller than the pivot, while the j pointer iterates through the list. When an element smaller than or equal to the pivot is found, it’s swapped with the element at index i+1. Finally, the pivot is placed at its correct position by swapping it with the element at i+1. The function returns the index of the pivot after partitioning.

Method 2: Creating New Lists with List Comprehensions

This method creates three new lists: one for elements less than the pivot, one for elements equal to the pivot, and one for elements greater than the pivot. It’s less memory-efficient than in-place partitioning but can be more readable.

 def partition_new_lists(arr, pivot):
     """
     Partitions the array 'arr' around a pivot by creating new lists.

     Args:
         arr (list): The list to partition.
         pivot (any): The pivot value.

     Returns:
         list: A new list partitioned around the pivot.
     """
     less = [i for i in arr if i < pivot]
     equal = [i for i in arr if i == pivot]
     greater = [i for i in arr if i > pivot]
     return less + equal + greater

 # Example usage:
 arr = [5, 2, 8, 1, 9, 4, 5, 7]
 pivot = 5
 partitioned_arr = partition_new_lists(arr, pivot)
 print("Partitioned array:", partitioned_arr)
 

 Partitioned array: [2, 1, 4, 5, 5, 8, 9, 7]
 

Explanation: The partition_new_lists function uses list comprehensions to create three new lists: less, equal, and greater. These lists contain elements less than, equal to, and greater than the pivot, respectively. The function then concatenates these lists in the order less + equal + greater and returns the resulting partitioned list.

Method 3: Using Filter and Lambda Functions

This method uses the `filter` function with lambda functions to achieve partitioning. It’s another way to create new lists based on the pivot.

 def partition_filter_lambda(arr, pivot):
     """
     Partitions the array 'arr' around a pivot using filter and lambda functions.

     Args:
         arr (list): The list to partition.
         pivot (any): The pivot value.

     Returns:
         list: A new list partitioned around the pivot.
     """
     less = list(filter(lambda x: x < pivot, arr))
     equal = list(filter(lambda x: x == pivot, arr))
     greater = list(filter(lambda x: x > pivot, arr))
     return less + equal + greater

 # Example usage:
 arr = [5, 2, 8, 1, 9, 4, 5, 7]
 pivot = 5
 partitioned_arr = partition_filter_lambda(arr, pivot)
 print("Partitioned array:", partitioned_arr)
 

 Partitioned array: [2, 1, 4, 5, 5, 8, 9, 7]
 

Explanation: The partition_filter_lambda function uses the filter function along with lambda functions to filter the elements of the input list based on whether they are less than, equal to, or greater than the pivot. It then concatenates the resulting lists in the order less + equal + greater to create the partitioned list.

Method 4: Lomuto Partition Scheme

The Lomuto partition scheme is another in-place partitioning algorithm commonly used in Quicksort. It’s similar to Method 1 but uses a slightly different approach for swapping elements.

 def lomuto_partition(arr, low, high):
     """
     Partitions the array 'arr' in-place around a pivot using the Lomuto partition scheme.

     Args:
         arr (list): The list to partition.
         low (int): The starting index of the partition.
         high (int): The ending index of the partition.

     Returns:
         int: The index of the pivot after partitioning.
     """
     pivot = arr[high]
     i = low - 1

     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

 # Example usage:
 arr = [5, 2, 8, 1, 9, 4, 7]
 n = len(arr)
 pivot_index = lomuto_partition(arr, 0, n - 1)
 print("Partitioned array:", arr)
 print("Pivot index:", pivot_index)
 

 Partitioned array: [2, 1, 4, 5, 9, 8, 7]
 Pivot index: 3
 

Explanation: The lomuto_partition function implements the Lomuto partition scheme. It iterates through the array and swaps elements smaller than the pivot to the left side of the partition. The index `i` keeps track of the boundary between smaller and larger elements. Finally, the pivot is swapped into its correct position, and the pivot index is returned.

Method 5: Hoare Partition Scheme

The Hoare partition scheme is another in-place partitioning algorithm that’s often considered more efficient than Lomuto’s scheme. It uses two indices that move towards each other from opposite ends of the array.

 def hoare_partition(arr, low, high):
     """
     Partitions the array 'arr' in-place around a pivot using the Hoare partition scheme.

     Args:
         arr (list): The list to partition.
         low (int): The starting index of the partition.
         high (int): The ending index of the partition.

     Returns:
         int: The index of the pivot after partitioning.
     """
     pivot = arr[low]  # Choose the first element as the pivot
     i = low - 1
     j = high + 1

     while True:
         # Find the leftmost element greater than or equal to the pivot
         while True:
             i += 1
             if arr[i] >= pivot:
                 break

         # Find the rightmost element smaller than or equal to the pivot
         while True:
             j -= 1
             if arr[j] <= pivot:
                 break

         if i >= j:
             return j

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

 # Example usage:
 arr = [5, 2, 8, 1, 9, 4, 7]
 n = len(arr)
 pivot_index = hoare_partition(arr, 0, n - 1)
 print("Partitioned array:", arr)
 print("Pivot index:", pivot_index)
 

 Partitioned array: [1, 2, 4, 5, 9, 8, 7]
 Pivot index: 3
 

Explanation: The hoare_partition function implements the Hoare partition scheme. It uses two pointers, `i` and `j`, starting from the low and high ends of the array, respectively. The `i` pointer moves right until it finds an element greater than or equal to the pivot, and the `j` pointer moves left until it finds an element smaller than or equal to the pivot. If `i` and `j` haven’t crossed, the elements at `i` and `j` are swapped. The process continues until `i` and `j` cross, at which point the index `j` is returned. Note that Hoare partitioning may not place the pivot element in its final sorted position.