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 similar problem before as Segregate 0s and 1s in an array. We explored how to count elements and re-write them again on to 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 index, 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 algorithm 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)

3-way quicksort

In post Dutch National Flag Algorithm, we discussed how can we sort and 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 that quick sort relies on partitioning of input and input is partitioned in  two parts. What if we divide input space in three parts? Then it becomes 3-way quicksort.

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

Quicksort basics and limitation

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

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

  • 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 partitioned array goes lower than 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 inout array contains lot of duplicate values which is very frequent in real world. Idea is to divide array in three parts rather than two. Let’s say P be pivot. First part contains all numbers which are less than p, second part contains number equal to p and last part contains numbers which are greater than p.

3-way quicksort algorithm 

3-way quicksort is optimization which works in specific cases like when input to be sorted contains few unique keys, in this case having traditional approach of one pivot does not perform well compared to 3-way quicksort.
Some of the properties of 3-way quicksort are:
It is not stable, when stability is the requirement, avoid using quicksort in general.
It uses O(lg(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
Best part is it takes O(n) time when O(1) unique keys.

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

3-way quicksort

3-way quicksort Implementation

#include <stdio.h>

int min(int a, int b){
 if(a > b) 
    return b;
  return a;
}

void swap(int a[], int i, int j){
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

void quicksort(int a[], int low, int high){
	int pivot = a[high];
	
	int lt = low;
	int reader = low ;
	int gt = high;
	
	while(reader < gt){
		if(a[reader] < pivot){
			swap(a, reader, lt);
			reader++;
			lt++;
		}
		else if(a[reader] == pivot){
			gt--;
		    swap(a, reader, gt);
		}
		else{
			reader++;
		}
	}
  
	int minimum = min( gt-lt, high-gt+1);
	for(int i=0; i<minimum; i++){
		swap(a, lt+i, high-minimum+1+i); 
	}

	if( low < high){
		quicksort(a, low, lt-1);
   		quicksort(a, high-gt+lt, high);
	}
	return ;
}

int main(void) {
	int a[] = {4,3,3,2,7,9,2,3,5,6,7,4};
	int size = sizeof(a)/sizeof(a[0]);

	quicksort(a, 0, size-1);
	
	printf("\n");
	for(int i=0; i<size; i++){
		printf("%d ", a[i]);	
	}

	return 0;
}

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.