The Dutch National Flag Problem

The Dutch national flag problem (DNF) is a 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 the same color are together and their collective color groups are in the correct order.

This solution to this problem is of interest for designing sorting algorithms; in particular, the quicksort algorithm  which may use a three-way partitioning function that groups items less than a given key (red), equal to the key (white) and greater than the key (blue).

The problem can be though of in programming as follows: 

Write a program that takes in an array A and an index i into A, and rearrange the elements such that all the elements less than A[i]  (“the pivot”) appear first, followed by elements equal to the pivot, proceeded by elements greater  than the pivot. 

I recommend you step through the code to get a better understanding of what is happening. Here is a online visualized that may help: http://www.pythontutor.com/visualize.html#mode=edit

Solution:

Approach 1 (Trivial): 

Time: O(n) & Space: O(n)

We form three lists for each section of the “flag” (less than, equal to, greater than). Iterating through A and adding the elements to their subsequent lists. Consequently, writing these values into A.

Approach 2: 

Time: O(n^2) & Space: O(1)

We can avoid using O(n) additional space at the cost of increased time as follows. At first we iterate through A starting from start of the list. In each iteration, seek an element smaller than the pivot — as soon as we find it, move it to the sub-array of smaller elements via exchange. This moves all the smaller elements to the to the start of the array. The second stage is similar to the first one, the difference being that we move elements greater than the pivot to the end of the array.

def dutch_flag(Arr, pivot_index):
    pivot = Arr[pivot_index]
    # First pass for elements less than pivot
    for i in range(len(Arr)):
        # Look for a smaller element
        for k in range(i+1, len(Arr)):
            if Arr[k] < pivot:
                Arr[i], Arr[k] = Arr[k], Arr[i] 
                break
    # Second Pass for elements greater than pivot
    for i  in reversed(range(len(Arr))):
        if Arr[i] < pivot:
            break
        # Look for a larger element. Stop when we reach an element 
        #less than pivot, since first pass has moved them to the 
        #start of A.
        for k in reversed(range(i)):
            if Arr[k] > pivot:
                Arr[i], Arr[k] = Arr[k], Arr[i]
                break

Approach 2 Improved: Intuitively, this approach has bad time complexity because in the first pass when searching for each additional element smaller than the pivot we start from the beginning, However, there is no reason to start from so far back-we can begin from the last location we advanced to. (Similar comments hold for the second pass.)To improve time complexity, we make a single pass and move all the elements less than the pivot to the beginning. In the second pass we move the larger elements to the end. It is easy to perform each pass in a single iteration, moving out-of-place elements as soon as they are discovered

def dutch_flag(Arr, pivot_index):
    pivot = Arr[pivot_index]
    # First pass for elements less than pivot
    smaller = 0
    for i in range(len(Arr)):
        # Look for a smaller element
        if Arr[i] < pivot:
                Arr[i], Arr[smaller] = Arr[smaller], Arr[i] 
                smaller += 1
    # Second Pass for elements greater than pivot
    larger = len(Arr) -1
    for i  in reversed(range(len(Arr))):
        if Arr[i] < pivot:
            break
        elif Arr[i] > pivot:
                Arr[i], Arr[larger] = Arr[larger], Arr[i]
                larger -= 1

Approach 3 is similar to the one above, the difference being it performs the classification into elements less than, equal to, and greater than the pivot in a single pass. We do this by maintaining four sub-arrays: bottom (elements less than pivot), middle (elements equal to pivot), unclassified, and top (elements greater than pivot). Initially, all elements are in unclassified. We iterate through elements in unclassified, and move elements into one of bottom, middle, and top groups according to the relative order between the incoming unclassified element and the pivot.

def dutch_flag(A, pivot_index):
    pivot = A[pivot_index]
    # Keep the following invariants during partitioning
    # bottom group: A[:smaller]
    # middle group: A[smaller:equal]
    # unclassified group: Arr[equal:larger]
    # top group: A[larger:]
    smaller, equal, larger = 0, 0, len(A)
    # Keep iterating as long as there is an unclassified element
    while equal < larger:
        # A[equal] is the upcoming unclassified element
        if A[equal] < pivot:
            A[smaller], A[equal] = A[equal], A[smaller]
            smaller, equal = smaller + 1, equal + 1
        elif A[equal] == pivot:
            equal += 1
        else: # A[equal] > pivot
            larger -= 1
            A[equal], A[larger] = A[larger], A[equal]

Each iteration decreases the size of unclassified by 1,, and the time spent within each iteration is O(1), implying the time complexity is O(n). The space complexity is clearly O(1)