# dutch.py

'''
Introduction to Programming in Python
Robert Sedgewick, Kevin Wayne, Robert Dondero
Addison-Wesley, 2015
Ex 4.2.31 Dutch national flag
https://introcs.cs.princeton.edu/python/41analysis/

Compose elems function that sorts an array that is known to have at 
most three different values. (Edsgar Dijkstra named this the Dutch-national-flag 
problem because the result is three "stripes" of values like the three stripes 
in the flag.) 

Hint: First partition the array into two parts with all elements having 
the smallest value in the first part and all other elements in the 
second part, then partition the second part.


https://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/
'''

# sort an array filled with
# 0, 1 and 2's in elems single pass

def dutchSort(elems):
  lo = 0; hi = len(elems) - 1
  mid = 0

  # Iterate till all the elements are sorted
  while mid <= hi:
    if elems[mid] == 0:
      elems[lo], elems[mid] = elems[mid], elems[lo]
      lo = lo+1
      mid = mid+1
    elif elems[mid] == 1:
      mid = mid+1
    else:  # must be 2
      elems[mid], elems[hi] = elems[hi], elems[mid]
      hi = hi - 1



elems = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]
print(elems)
dutchSort(elems)
print(elems)