Dutch National Flag Problem

https://www.cnblogs.com/evasean/p/7217623.html

第二周课程的Elementray Sorts部分练习测验Interview Questions的第3题荷兰国旗问题很有意思。题目的原文描述如下：

Dutch national flag. Given an array of n buckets, each containing a red, white, or blue pebble, sort them by color. The allowed operations are:

• swap(i,j): swap the pebble in bucket i with the pebble in bucket j
• color(i)determine the color of the pebble in bucket i

The performance requirements are as follows:

• At most n calls to color()
• At most n calls to swap()
• Constant extra space.

该问题在维基百科上的解释为：

The Dutch national flag problem (DNF) is a computer science programming problem proposed by Edsger Dijkstra.The flag of the Netherlands consists of three colors: red, white and blue. Given balls of these three colors arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order.

 1     public void quickSort3way(){
 2         int lt = 0;
 3         int gt = n - 1;
 4         int i = 0;
 5         while (i <= gt) {
 6             int cc = color(i);
 7             if(cc < WHITE) swap(lt++,i++);
 8             else if(cc > WHITE) swap(i,gt--);
 9             else i++;
10         }
11     }

Two Colours

It is easiest to consider just two "colours", {zero,one}, first. The algorithm maintains three sections (possibly empty) in the array a[ ]:

1. a[1..Lo-1] zeroes
2. a[Lo..Hi] unknown
3. a[Hi+1..N] ones

The unknown section is shrunk while maintaining these conditions:

1. Lo := 1; Hi := N;
2. while Lo <= Hi do
   1. Invariant: a[1..Lo-1] are all zero and a[Hi+1..N] are all one; a[Lo..Hi] are unknown.
   2. if a[Lo] = 0 then Lo++
   3. else swap a[Lo] and a[Hi]; Hi--

The problem was posed with three colours, here `0', `1' and `2'. The array is divided into four sections:

1. a[1..Lo-1] zeroes (red)
2. a[Lo..Mid-] ones (white)
3. a[Mid..Hi] unknown
4. a[Hi+1..N] twos (blue)

The unknown region is shrunk while maintaining these conditions

1. Lo := 1; Mid := 1; Hi := N;
2. while Mid <= Hi do
   1. Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2; a[Mid..Hi] are unknown.
   2. case a[Mid] in
      • 0: swap a[Lo] and a[Mid]; Lo++; Mid++
      • 1: Mid++
      • 2: swap a[Mid] and a[Hi]; Hi--

https://sites.google.com/site/csharpofjameschen/home/sort/threewayssort--amazon
http://www.careercup.com/question?id=21037663

Given an array of numbers, arrange it such that all the numbers less than a given key should come before the key and all the numbers greater than the key should come after it. 

For example: arr = { 0, -1, -2, 2, 0, 3, 5}, given key = 0 

answer should be {-1, -2, 0, 0, 2, 3, 5} 

Order of elements that are smaller or greater than key does not matter i.e. sorting is not expected. So, {-1,-2, 0, 0, 5, 2, 3} is also a correct answer. 

Time complexity should not be more than O(n).

        static void Swap(ref int i, ref int j)

        {

            int temp = i;

            i = j;

            j = temp;

        }

        static void Sort(int[] a, int key)

        {

            int bottom = -1;

            int top = a.Length;

            int i = 0;

            while (i < top)

            {

                if (a[i] > key)

                {

                    Swap(ref a[i], ref a[--top]);

                }

                else if (a[i] == key)

                {

                    i++;

                }

                else

                {

                    Swap(ref a[++bottom], ref a[i]);

                    i++;

                }

            }     

        }

http://www.zrzahid.com/dutch-national-flag-dnf-problem-3-way-partitioning/

public static void DNFSort(int a[]){
 int p1 = 0;
 int p2 = 0;
 int p3 = a.length-1;
 
 while(p2 <= p3){
  if(a[p2] == 0){
   swap(a, p2, p1);
   p1++;
   p2++;
  }
  else if(a[p2] == 1){
   p2++;
  }
  else if(a[p2] == 2){
   swap(a, p2, p3);
   p3--;
  }
 }
}

public void threeWayPartition(int[] arr, int key) {
 int low = 0;
 int high = arr.length - 1;
 for (int lookAt = 0; lookAt <= high;) {
  if (arr[lookAt] < key) {
   swap(arr, lookAt++, low++);
  } else if (arr[lookAt] > key) {
   swap(arr, lookAt, high--);
  } else {
   ++lookAt;
  }
 }
 
 void swap(int[] arr, int p1, int p2) {
  int temp = arr[p1];
  arr[p1] = arr[p2];
  arr[p2] = temp;
 }

Read full article from Dutch National Flag Problem