sorts.dutch_national_flag_sort

A pure implementation of Dutch national flag (DNF) sort algorithm in Python. Dutch National Flag algorithm is an algorithm originally designed by Edsger Dijkstra. It is the most optimal sort for 3 unique values (eg. 0, 1, 2) in a sequence. DNF can sort a sequence of n size with [0 <= a[i] <= 2] at guaranteed O(n) complexity in a single pass.

The flag of the Netherlands consists of three colors: white, red, and blue. The task is to randomly arrange balls of white, red, and blue in such a way that balls of the same color are placed together. DNF sorts a sequence of 0, 1, and 2’s in linear time that does not consume any extra space. This algorithm can be implemented only on a sequence that contains three unique elements.

1. Time complexity is O(n).

2. Space complexity is O(1).

More info on: https://en.wikipedia.org/wiki/Dutch_national_flag_problem

For doctests run following command: python3 -m doctest -v dutch_national_flag_sort.py

For manual testing run: python dnf_sort.py

Attributes

blue
colors
red
user_input
white

Functions

dutch_national_flag_sort(→ list)

A pure Python implementation of Dutch National Flag sort algorithm.

Module Contents

sorts.dutch_national_flag_sort.dutch_national_flag_sort(sequence: list) → list

A pure Python implementation of Dutch National Flag sort algorithm. :param data: 3 unique integer values (e.g., 0, 1, 2) in an sequence :return: The same collection in ascending order

>>> dutch_national_flag_sort([])
[]
>>> dutch_national_flag_sort([0])
[0]
>>> dutch_national_flag_sort([2, 1, 0, 0, 1, 2])
[0, 0, 1, 1, 2, 2]
>>> dutch_national_flag_sort([0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1])
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2]
>>> dutch_national_flag_sort("abacab")
Traceback (most recent call last):
  ...
ValueError: The elements inside the sequence must contains only (0, 1, 2) values
>>> dutch_national_flag_sort("Abacab")
Traceback (most recent call last):
  ...
ValueError: The elements inside the sequence must contains only (0, 1, 2) values
>>> dutch_national_flag_sort([3, 2, 3, 1, 3, 0, 3])
Traceback (most recent call last):
  ...
ValueError: The elements inside the sequence must contains only (0, 1, 2) values
>>> dutch_national_flag_sort([-1, 2, -1, 1, -1, 0, -1])
Traceback (most recent call last):
  ...
ValueError: The elements inside the sequence must contains only (0, 1, 2) values
>>> dutch_national_flag_sort([1.1, 2, 1.1, 1, 1.1, 0, 1.1])
Traceback (most recent call last):
  ...
ValueError: The elements inside the sequence must contains only (0, 1, 2) values

sorts.dutch_national_flag_sort.blue = 2

sorts.dutch_national_flag_sort.colors

sorts.dutch_national_flag_sort.red = 0

sorts.dutch_national_flag_sort.user_input

sorts.dutch_national_flag_sort.white = 1