Here is the problematic flag:

It certainly does not says what the problem is. It's actually a three way partitioning problem.

So, here is algorithm for three way partitioning:

[1] View longer discussion at Wikipedia

[2] View/download Java code from GitHub

It certainly does not says what the problem is. It's actually a three way partitioning problem.

**Definition:**An array`A[1..n]`

needs to be rearranged in such a way that moving from left to right, we see three subgroups in this order: `(-∞, low), [low, high], (high, ∞)`

.**Algorithm:**I came to this solution while working on a StackOverflow question about rearranging an array in such that all the elements less than zero are in left zero; and all the elements greater than zero lies to the right of it. My initial intuition was that I can do it by the improvising the partition part of Quicksort mechanism. It turns out while partitioning works for single pivot element. If you have a dupe of pivot, it may not work.So, here is algorithm for three way partitioning:

A[1..n] def three-way-part (A, low, high): left = 0 right = n+1 i = 1 while i < right : if A[i] < low : swap(i, ++left) else if A[i] > high : swap(i, --right) else : i++

**Complexity:**Time complexity:`O(n)`

, space complexity: `O(1)`

**Footnote:**[1] View longer discussion at Wikipedia

[2] View/download Java code from GitHub

there is no any color comparison (i.e red,white,blue)

ReplyDelete