Monday, October 22, 2012

Dutch National Flag Problem

Here is the problematic flag:


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

1 comment: