UniLecs #180. Задача флага Нидерландов

Задача флага Нидерландов(Dutch national flag problem, DNF) — задача дискретной математики, которую предложил Эдсгер Дейкстра. Флаг Нидерландов состоит из трех цветов: красного, белого и синего. Получая шары этих трех цветов, расположенных в случайном порядке, задача состоит в том, чтобы организовать их таким образом, что все шары одного цвета были вместе, а их общие цвета шли в порядке как на данном флаге.

Задача: дан массив, содержащий только числа 0, 1, 2. Необходимо отсортировать массив по возрастанию. 

Условие: для преобразования использовать исходный массив.

Входные данные: массив, состоящий только из набора чисел 0, 1 и 2.

Вывод: отсортированный по возрастанию массив

Пример:

Input = [ 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 ]

Output= [ 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2 ]

Идея: Простым и наиболее понятным решением была бы обычная сортировка, но для этого потребуется два обхода по массиву.

Но можно переставить массив за один проход, разделяя значения на три группы:

• значения меньше, чем 1
• значения, равные 1
• значения больше 1.

Реализация:

Бонусом представлена реализация сортировки по убыванию (смотри gist-файл)

https://gist.github.com/unilecs/20efb90650b4da83363cd4eb1e00ff27

Play-test: https://dotnetfiddle.net/geUa1L