- 490,034 hits
Make the frequent cases fast and the rare case correct
Dutch National Flag Problem – Python
October 16, 2011Posted by on
The Dutch national flag problem is a famous computer science related 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 same color are together and their collective color groups are in the correct order – Wikipedia
The Problem can be reconstructed for a given list consisting 0s, 1s and 2s write a function thats displays 0s first, then 1s and rest of the 2s in last.
0 – Red
1 – White
2 – Blue
def DNF(input,length): high = length - 1 p = 0 i = 0 while i <= high: if input[i] == 0: input[i],input[p]=input[p],input[i] p = p+1 i = i+1 elif input[i] == 2: input[i],input[high]=input[high],input[i] high = high-1 else: i = i+1 input = [0,1,2,2,1,0] print "input: ", input DNF(input,len(input)) print "output: ", input
~/DNF$ python dnf.py
input: [0, 1, 2, 2, 1, 0]
output: [0, 0, 1, 1, 2, 2]
Further reading : Article from Monash
DNF algorithm can be used in Quicksort to partition the elements. DNF algorithm makes O(n) moves and examinations.