Сортировка «Двухцветный флаг» :: Bicolor Flag Sort

Более простая версия задачи голландского национального флага (два разряда вместо трёх), которая в свою очередь является упрощённой версией сортировки «Американский флаг» (три разряда вместо произвольного количества разрядов).

Это не сортировка в привычном понимании, а алгоритм, распределяющий числа по двум разрядам: младший разряд - условный 0 и старший разряд - условная 1.

На ключи массива устанавливаются два указателя. В начале массива находится указатель на младший разряд, в конце - на старший.

Затем происходит просмотр слева-направо элементов массива. Если очередной элемент соответствует младшему разряду, то указатель младшего разряда сдвигается на одну позицию вправо. Если очередной элемент соответствует старшему разряду, то осуществляется обмен с числом, на которое указывает указатель для старших разрядов, а сам указатель старшего разряда сдвигается на одну позицию влево.

Ссылки

Сортировка «Американский флаг»