Dutch National Flag Problem

Dutch National Flag Problem

Given an array with 0s,1s and 2s, sort array in increasing order. Another way to phrase this problem is sort balls with three different colors : red, blue and white, where balls of each color are placed together. This is typically know as Dutch national flag problem and algorithm to solve it is called Dutch national flag problem. Example:
A = [0,1,0,1,1,2,0,2,0,1] Output = [0,0,0,0,1,1,1,1,2,2]
A = [R,B,B,W,B,R,W,B,B] Output = [R,R,W,W,B,B,B,B]
This problem can be asked as design question, as let’s say you have to design a robot. All this robot does is : it see three empty buckets and a bucket full of colored balls (red, blue and white). Design an instruction set for this robot that it fill each empty buckets with one color. It’s the same problem as Dutch National Flag problem.

Count to sort an array of 0s,1s and 2s
We have already seen a similar problem before as Segregate 0s and 1s in an array. We explored how to count elements and re-write them again on to the array.

Let’s apply the same method for this problem. Take an array of three integers, index store corresponding count for that number. E.g count[0] stores count of 0 and count[1] stores count of 1. Scan through the array and count each element. At last, re-write those numbers back on to array starting from index 0, according to their count. For example, if there are 4 zeros, then starting from 0 indexes, write 4 zeros, followed by 1s and then by 2.

Complexity of counting method is O(n), notice that we scan array twice, first time for counts and second time for writing on array.

Dutch national flag problem : algorithm

  1. Start with three pointers : reader, low and high.
  2. reader and low are initialized as 0 and high is initialized as last element of array as size-1.
  3. reader will be used to scan the array while low and high will be used to swap elements to their desired positions.
  4. Starting with current position of reader, follow below steps, keep in mind we need 0 at start of array
    1. If element at index reader is 0, swap element at reader with element at low and increment low and reader by 1.
    2. If element at reader is 1, do not swap and increment reader by 1.
    3. If element at reader is 2, swap element at reader with element at high and decrease high by 1

Actually, three pointers divide array into four parts.  Red, white, unknown and Blue. Every element is taken from unknown part and put into its right place. So all three other parts expand while unknown part shrinks.

Let’s take an example and see how dutch national flag algorithm works.

First step, initialize reader, low and high.

dutch national flag problem

Element at reader is 0, hence swap element at reader and low,also increment reader and low.

dutch national flag algorithm

Follow the same step, check element at reader again, it’s 1, hence, just move reader by one.

dutch national flag problem

Element at reader is now 2, swap element at reader with element at high and decrease high by 1.

dutch national flag problem

Element at reader is 1, just increment reader.

Element at reader is now 2, swap element at reader with element at high and decrease high by 1.

Dutch national flag algorithm explanation

Element at reader is 1, just increment reader.

dutch national flag problem

Element at reader is 1, just increment reader.

Dutch national flag algorithm explanation

Element at reader 0, hence swap element at reader and low,also increment reader and low.

dutch national flag problem

Element at reader 0, hence swap element at reader and low,also increment reader and low.

Dutch national flag algorithm explanation

Element at reader is now 2, swap element at reader with element at high and decrease high by 1.

dutch national flag problem

Here, high becomes less than reader, we can stop as array is already sorted.

Dutch national flag problem implementation

package com.company;

/**
 * Created by sangar on 5.1.18.
 */
public class DutchNationalFlag {

    public static void swap(int[] input, int i, int j){
        int temp =  input[i];
        input[i] = input[j];
        input[j] = temp;
    }

    public static void dutchNationalFalgAlgorithm(int [] input){

        //initialize all variables
        int reader = 0;
        int low = 0;
        int high = input.length - 1;

        while(reader <= high){
            /*
              input always holds a permutation of the 
              original data with input(0..(lo-1)) =0, 
              input(lo..(reader-1))=1, input(reader..hi) is
              untouched, and input((hi+1)..(input.length-1)) = 2
            */
            if(input[reader] == 0){
                /*When element at reader is 0, swap
                element at reader with element at index
                low and increment reader and low*/
                swap(input, reader, low);
                reader++;
                low++;
            }
            else if(input[reader] == 1){
                /* if element at reader is just
                increment reader by 1 */
                reader++;
            }
            else if(input[reader] == 2){
                /* If element at reader is 2, swap
                 element at reader with element at
                 high and decrease high by 1 */
                swap(input, reader, high);
                high--;
            }
            else{
               System.out.println("Bad input");
               break;
            }
        }

    }
    public static void main(String[] args) {
        int[] input = {2,2,1,1,0,0,0,1,1,2};

        dutchNationalFalgAlgorithm(input);

        for(int i=0; i<input.length; i++){
            System.out.print(" " + input[i]);
        }
    }
}

Complexity of Dutch National Flag algorithm is O(n), however, we scan the array only once.

Please share if you have some suggestions or comments. Sharing is caring.

3-way quicksort (Quick sort on non unique elements)

In the post on the Dutch National Flag Algorithm, we discussed how to sort an array in linear time by partitioning it in four parts, red, white, unknown and blue. Can we apply the same technique on quick sort.? As we all know, quick sort relies on the partitioning of input into two parts. What if we divide the input into three parts? Then it becomes a 3-way quicksort.

The 3-way partition variation of quick-sort has a slightly higher overhead compared to the standard 2-way partition version. Both have the same best, typical, and worst-case time bounds, but the 3-way version is highly adaptive in the very common case of sorting with many non-unique keys.

Quicksort basics and limitation

Before going ahead with 3-way partition method, I would strongly recommend that you go through the usual quick sort algorithm: Quicksort algorithm in C

A big limitation of quicksort is that it has O(n2) worst-case running time. Some improvements have been suggested as given below:

  • The cutoff to insertion sort. Switch to insertion sort for arrays with size less than a pre-decided limit. We follow quick sort and partition array. Once the size of the partitioned array goes lower than the limit, apply insertion sort on that array. Limit varies from system to system and typically it is between 5 to 15.
  • Median-of-three partitioning. Use median of a small sample of items taken from the array as the partitioning item. Doing so will give a slightly better partition but at the cost of computing the median.

There is another optimization which is called as Entropy-optimal sorting or 3-way partition quick sort. This method is useful when the input array contains a lot of duplicate values which can be frequently seen in the real world. The idea is to divide the array in three parts rather than two. Let’s say P is the pivot index. The first part contains all the numbers which are less than P, the second part contains number equal to P and the last part contains numbers which are greater than P.

3-way quicksort algorithm 

Some of the properties of the 3-way quicksort are:
It is not stable! Avoid using quicksort in cases where stability is essential.
It uses O(log(n)) extra space, why? Because of the recursion.
Worst case run time is as same as classic quicksort, O(n2), but typically O(nlog(n)) time
The best part is that it takes O(n) time when O(1) unique keys.

This algorithm partitions the array into three parts:
1. one with is less than pivot
2. equal to pivot
3. one with elements greater than the pivot

3-way quicksort

3-way quicksort Implementation

 
import java.util.Arrays;
import java.util.Stack;
 
/**
 * Created by sangar on 18.9.18.
 */
public class StockSpan {
    public static int[] stockSpan(int[] prices){
 
        Stack<Integer> s = new Stack();
        int[] span = new int[prices.length];
 
        //Step 1. Initialization
        span[0] = 1;
        s.push(0);
 
        for(int i=1; i<prices.length; i++){
            //Find the price on stack which is greater than current day's price
            while(!s.empty() && prices[i] > prices[s.peek()])
                s.pop();
 
            if(s.empty())
                span[i] = i+1;
            else
                span[i] =  i - s.peek();
 
            //Push current day onto top of stack
            s.push(i);
        }
 
        return span;
    }
 
    public static void main(String args[]){
        int prices[] = {100, 60, 70, 65, 80, 85, 45, 77, 56, 98, 200};
        int[] span = stockSpan(prices);
 
        Arrays.stream(span).forEach(System.out::println);
 
    }
}

The complexity of 3-way quicksort is O(n2).

Please share if something is wrong or any other suggestion or query. We would love to hear what you have to say.