Сортировка «Флаг Нидерландов» :: Dutch Flag Sort
Более простая версия сортировки «Американский флаг» (три разряда вместо произвольного количества разрядов). Алгоритм для двухцветного флага - упрощённая версия по сравнению с голландским.
Это не сортировка в привычном понимании, а алгоритм, распределяющий числа по трём разрядам: младший разряд - условный 0, средний разряд - условная 1 и старший разряд - условная 2.
На ключи массива устанавливаются три указателя. В начале массива находятся указатели на младший и средний разряды, в конце - на старший.
Затем происходит просмотр слева-направо элементов массива. Если очередной элемент соответствует младшему разряду, то указатель младшего разряда сдвигается на одну позицию вправо. Если очередной элемент соответствует среднему разряду, то осуществляется обмен с числом, на которое указывает указатель для среднего разряда, а сам указатель среднего разряда сдвигается на одну позицию вправо. Если очередной элемент соответствует старшему разряду, то осуществляется обмен с числом, на которое указывает указатель для старших разрядов, а сам указатель старшего разряда сдвигается на одну позицию влево.
Dutch national flag problem