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

OUTPUT:

~/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.

### Like this:

Like Loading...

*Related*

test [1,2,0], then u see the bug

change to while i <= high:

good luck

Thanksđź™‚ i made the change

def DNF(input, length, Swaps=0):

high = length – 1

p = 0

i = 0

while i <= high:

if input[i] == 0:

if input[i]==input[p]:

p+=1

i+=1

else:

input[i],input[p]=input[p],input[i]

p = p+1

i = i+1

Swaps+=1

elif input[i] == 2:

if input[i]==input[high]:

high-=1

else:

input[i],input[high]=input[high],input[i]

high = high-1

Swaps+=1

else:

i = i+1

print "Swaps",Swaps

input = [1,1,0,2,2]

DNF(input,len(input))

print input