Сортировка «Американский флаг» :: American Flag Sort
Более простые версии этой сортировки - двухцветный флаг и трёхцветный голландский флаг. Визуализация очень похожа на сортировку аппроксимацией.
При первом проходе — поиск максимума с целью определить максимальное количество разрядов среди элементов в массиве (для того чтобы корректно извлекать определённые по счёту разряды из элементов).
Затем происходит рекурсивная обработка. При вызове указываются границы подмассива и текущий обрабатываемый разряд. На первом вызове подмассивом является весь массив, берётся самый первый разряд слева.
Среди элементов подмассива осуществляется начальный подсчёт — сколько раз каждая цифра встречается в текущем разряде. Этот посдчёт позволяет определить локализации для этих цифр разрядов (т.е. известны пределы и местонахождение «полосы», в которую нужно переместить те элементы, которые имеют очередную цифру в определённом разряде). Собственно, локализации — это указатели на «полосы», куда нужно перемещать соответствующие элементы.
В соответствии с локализациями-указателями происходит обмен на месте — по цифре в разряде видно, куда нужно отправить элемент, на его место приходит другой элемент, с которым произошёл обмен. Этот пункт выполняется до тех пор, пока при очередном обмене пришедший из другого места элемент не окажется на своём месте (тогда можно переходить к следующему элементу подмассива и аналогично для него выполнить этот пункт).
После того, как в результате обменов перераспределили элементы в блоки по цифрам в очередном разряде, происходит рекурсия — к каждому блоку как к подмассиву применяется этот же алгоритм, в качестве текущего разряда берётся следующий по счёту.
American flag sort