Linear-time partition is a `divide & conquer`

based selection algorithm. With it, data is split into three groups using a pivot.

Quote:An integral part of

`Quick Sort`

algorithm 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 the 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 make use of this fact, like:

- Sort an array that contains only 0s, 1s & 2s
- Dutch national flag problem
- Print all negative integers followed by positive for an array full of them
- Print all 0s first and then 1s or vice-versa for an array with only 0s & 1s
- Move all the 0s to the end maintaining relative order of other elements for an array of integers

Quote:If done out of place, (i.e. not changing the original data), it would cost

`O(`

additional spacen)

### Example

Let’s take an example of: sort an array that contains only 0s, 1s & 2s

First thought for such problem is to perform a count of 0s, 1s and 2s. Once we have the counts, reset the array with them. Though it has time complexity `O(n)`

, it takes two traversals 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 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 0s 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 the 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!.