Linear-time partition is a divide & conquer based selection algorithm. With it, data is split into three groups using a pivot.
.
An integral part of
Quick Sortalgorithm which uses this partitioning logic recursively. All the elements smaller than the pivot are put on one side and all the larger ones on the other side of the pivot.
Similar to discussion of Dynamic Programming, this algorithm plays on solving sub-problems to solve complex problem.
Algorithm
Post selecting the pivot, Linear-time partition routine separates the data into three groups with values:
- less than the pivot
- equal to the pivot
- greater than the pivot
Generally, this algorithm is done in place. This results in partially sorting the data. There are handful of problems that makes use of this fact, like:
- Sort an array that contains only 0’s, 1’s & 2’s
- Dutch national flag problem
- Print all negative integers followed by positive for an array full of them
- Print all 0’s first and then 1’s or vice-versa for an array with only 0’s & 1’s
- Move all the 0’s to the end maintaining relative order of other elements for an array of integers
If done out of place, (i.e. not changing the original data), it would cost
O(n)additional space
Example
Let’s take an example of: sort a array that contains only 0’s, 1’s & 2’s
First thought for such problem is to perform a count of 0’s, 1’s and 2’s. Once we have the counts, reset the array with them. Though it has time complexity O(n), it takes two traversal of the array or uses an extra array.
Below is an attempt to solve using Linear-time partition algorithm to avoid that extra traversal/space.
def threeWayPartition(A):
start = mid = 0
end = len(A)-1
# define a Pivot
pivot = 1
while (mid <= end):
# mid element is less than pivot
# current element is 0
# so lets move it to start
# current start is good.
# move start to next element
# move mid to next element to move forward
if (A[mid] < pivot) :
swap(A, start, mid)
start = start + 1
mid = mid + 1
# mid element is more than pivot
# current element is 2
# so lets move it to end
# current end is good.
# move end to previous element
elif (A[mid] > pivot) :
swap(A, mid, end)
end = end - 1
# mid element is same as pivot
# current element is 1
# just move forward:
# mid to next element
else :
mid = mid + 1
# Swap two elements A[i] and A[j] in the list
def swap(A, i, j):
A[i], A[j] = A[j], A[i]
# Define an array
inputArray = [0, 1, 2, 2, 1, 0, 0, 2]
# Call the Linear-time partition routine
threeWayPartition(inputArray)
# print the final result
print(inputArray)
# Outputs
# [0, 0, 0, 1, 1, 2, 2, 2]
With a defined pivot, we segregated the data on the either side which resulted in desired output. Dutch nation flag problem or printing all negative first and then positive, or printing all 0s first follows the same code.
For moving all 0’s to end maintaining other elements order, we do a tweak in swap index to maintain order:
def threeWayPartition(A):
current = 0
nonzero = 0
end = len(A)-1
# define a Pivot
pivot = 0
while (current <= end):
if (A[current] != pivot) :
swap(A, current, nonzero)
nonzero = nonzero + 1
current = current + 1
# Swap two elements A[i] and A[j] in the list
def swap(A, i, j):
A[i], A[j] = A[j], A[i]
# Define an array
inputArray = [7,0,5,1,2,0,2,0,6]
# Call the Linear-time partition routine
threeWayPartition(inputArray)
# print the final result
print(inputArray)
# Output
# [7, 5, 1, 2, 2, 6, 0, 0, 0]
Complexity
With above algorithm approach, we solved our problem with Time complexity O(n) & Space complexity O(1) (with single traversal of the array)
It was fun solving!