💡 Problem Formulation: The task is to rearrange an array such that all elements that are less than the lower bound of the given range are moved to the left, all elements that are within the range are in the middle, and those greater than the upper bound are moved to the right. An example input could be array = [1, 2, 3, 4, 5, 6, 7] with a range of (3, 6), and the desired output would rearrange the array to [1, 2, 3, 4, 5, 6, 7] with elements organized around the range boundaries.
Method 1: Two-Pointer Approach
Using the two-pointer approach, one can efficiently partition the array by iterating over the array with two markers that define the bounds for elements less than the lower bound and greater than the upper bound. This technique ensures a single pass over the elements leading to an optimal solution in respect of time complexity.
Here’s an example:
def three_way_partition(arr, low_val, high_val):
start = 0
end = len(arr) - 1
i = 0
while i <= end:
if arr[i] high_val:
arr[i], arr[end] = arr[end], arr[i]
end -= 1
else:
i += 1
return arr
# Example usage:
print(three_way_partition([1, 2, 3, 4, 5, 6, 7], 3, 6))
Output: [1, 2, 3, 4, 5, 6, 7]
This method systematically swaps elements with the start and end pointers, which effectively places them in their correct partitions without the need for extra space, thus making it an in-place algorithm.
Method 2: Using a Temporary Array
The temporary array method involves creating a new array to store elements based on the three partitions. It provides a more intuitive approach but requires extra memory which may not be optimal for large arrays.
Here’s an example:
def three_way_partition_temp_array(arr, low_val, high_val):
less, equal, greater = [], [], []
for i in arr:
if i high_val: greater.append(i)
else: equal.append(i)
return less + equal + greater
# Example usage:
print(three_way_partition_temp_array([1, 2, 3, 4, 5, 6, 7], 3, 6))
Output: [1, 2, 3, 4, 5, 6, 7]
The code snippet shows a clear separation of the array elements into three distinct lists which are then combined to form the partitioned array. While this method is easy to understand, it requires additional space proportional to the size of the input array.
Method 3: Pivot-Based Quicksort Variation
A pivot-based Quicksort variation modifies the traditional Quicksort algorithm to have two pivots instead of one. It partitions the array into three parts and recursively sorts the lesser and greater elements. This can be slightly more complex to implement but is efficient for sorting the array as well as partitioning.
Here’s an example:
def partition(arr, low, high):
# Assume arr[low] is pivot1 and arr[high] is pivot2
i, j = low+1, high-1
k = i
while k <= j:
if arr[k] arr[high]:
arr[k], arr[j] = arr[j], arr[k]
j -= 1
k -= 1 # need to reprocess this element
k += 1
# Swap the pivots to their correct positions
arr[low], arr[i-1] = arr[i-1], arr[low]
arr[high], arr[j+1] = arr[j+1], arr[high]
# Return the indices of the pivots
return i-1, j+1
def quicksort_dual_pivot(arr, low, high):
if low < high:
# Partition the array and get the pivot indices
pi1, pi2 = partition(arr, low, high)
# Recursively sort the parts
quicksort_dual_pivot(arr, low, pi1-1)
quicksort_dual_pivot(arr, pi1+1, pi2-1)
quicksort_dual_pivot(arr, pi2+1, high)
# Example usage:
arr = [1, 2, 3, 4, 5, 6, 7]
quicksort_dual_pivot(arr, 0, len(arr)-1)
print(arr)
Output: [1, 2, 3, 4, 5, 6, 7]
This snippet effectively partitions and sorts the array using the dual-pivot Quicksort method. It’s particularly good for large arrays as it organizes and sorts the array in one go, although the logic is more complex than the two-pointer approach.
Bonus One-Liner Method 5: List Comprehension
Python’s list comprehension can be used for a highly concise and readable one-liner that partitions an array, provided that the range is small and readability is preferred over performance.
Here’s an example:
low, high = 3, 6 arr = [1, 2, 3, 4, 5, 6, 7] partitioned = [x for x in arr if x < low] + [x for x in arr if low <= x high] print(partitioned)
Output: [1, 2, 3, 4, 5, 6, 7]
This one-liner approach uses list comprehension to create three separate lists and then concatenate them to form the partitioned list. It’s concise and easy to understand but should be used with caution for larger arrays due to possible performance implications.
Summary/Discussion
- Method 1: Two-Pointer Approach. Efficient with time complexity of O(n) and does not use extra space. It may not preserve the order of elements.
- Method 2: Using a Temporary Array. Intuitive with a clean separation of logic, but requires additional space which might not be appropriate for memory-sensitive applications.
- Method 3: Pivot-Based Quicksort Variation. Offers sorting in addition to partitioning, making it efficient for large arrays. However, the implementation complexity is higher.
- Method 5: List Comprehension. A one-liner pythonic way for readability and smaller ranges. Not the most performance-oriented for large data sets.