Dutch National Flag

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



Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s