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 colours: red, white and blue. Given balls of these three colours 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 colour are together and their collective colour groups are in the correct order.

Here is a problem that is stimulated by the idea:

Q. Write a function that takes an array A and index i into A, and rearranges the elements such that all elements less than A[i] appear first, followed by elements equal to A[i], followed by elements greater than A[i]. Your algorithm should have O(1) space complexity and O(|A|) time complexity.

Soln:

#Function to swap two variables
def swapNormal(A,pos1,pos2):
t = 0
t=A[pos1]
A[pos1] = A[pos2]
A[pos2] = t
#initializing an array of randomly generated numbers
j = 0
while j < 10:
A.append(random.randint(1,100))
j+= 1
print "The array of numbers is:",A
#asking for the position of the pivotal element
i = input("Please enter the index number")
pivot = A[i]
print "The pivot element is:",pivot
def dutchNationalFlag(A,pivot):
equal = 0
small = 0
large = len(A)-1
while (equal <= large):
if A[equal] < pivot:
swapNormal(A,equal,small)
equal += 1
small += 1
elif (A[equal] == pivot):
equal += 1
else:
swapNormal(A,equal,large)
large -= 1
return A

### Like this:

Like Loading...

*Related*