- PVSM.RU - https://www.pvsm.ru -
Чтобы понять принцип действия этой «многополосной» сортировки проще для начала разобраться на примере флага с тремя полосами. А чтобы легко разобраться с трёхцветным флагом, лучше сначала посмотреть, как это работает на примере двухцветного. А чтобы разобраться с двухцветным...
[1]
Статья написана при поддержке компании EDISON.Мы занимаемся портированием и миграцией программного обеспечения [2], а также разработкой мобильных приложений Android и iOS [3].
Мы очень любим теорию алгоритмов! ;-)
Для начала рассмотрим случай, когда числа в сортируемом массиве распределяются всего по двум разрядам. Для простоты примем, что у нас массив, состоящий из нулей (младший разряд) и единиц (старший разряд).
Таким образом у нас всего две «полосы»: в одну мы будем перемещать младшие разряды (нули), а в другую старшие разряды (единицы). Для демонстрации пойдёт любой двухцветный флаг. Например, флаг Украины.
Что тут происходит? Так как на первом этапе неизвестно, сколько у нас нулей и сколько единиц, поэтому непонятно, каких размеров в итоге окажется каждая из «полос». Поэтому ставим на ключи массива два указателя. Для младшего разряда указатель установлен на начало массива, для старшего — в конец. Затем делаем однократный проход по массиву слева-направо и смотрим каждый разряд-элемент.
Если при проходе элемент равен старшему разряду, то второй указатель нам подсказывает, куда нужно перенести этот элемент (производим обмен). Указатель для вставки следующего элемента перемещается влево, «полоса» для старшего разряда расширилась.
Если он равен младшему разряду, то указатель для него перемещаем на один элемент вправо. Так как у нас всего два разряда, перенесить элемент не приходится, он уже на своём месте. «Полоса» для младшего разряда естественным образом стала шире.
В итоге два указателя, движущихся навстречу друг другу, столкнутся в одной точке, а разряды будут упорядочены в своих «полосах». При этом не понадобится проход по всему массиву — когда произойдёт встреча указателей где-то в середине, алгоритм выполнит свою работу.
Слегка усложним задачу, рассмотрим не два разряда, а три. Пусть у нас элементы массива относятся к младшему (нули), среднему (единицы) и старшему (двойки) разрядам.
Для демонстрации возьмём трёхполосный красно-бело-синий флаг Франции Люксембурга России Шлезвиг-Гольдштейна Нидерландов. Почему именно флаг Нидерландов? Потому что Эдсгер Дейкстра в своих лекциях именно на примере этого флага рассмотрел соответствующий алгоритм, который был назван как «задача голландского национального флага».
Как видите, тут ничего особо нового. Для каждого разряда свой указатель. Иначально метки для младшего и среднего занимают стартовые позиции в начале массива и перемещаются вправо, когда встречается соответствующий элемент. Указатель для старшего разряда сначала находится в конце массива и движется влево.
Проход по массиву также по факту будет неполный, если разряды распределены более-менее равномерно, то алгоритм пройдёт 2/3 массива, прежде чем раскидает все элементы по своим «полосам».
Теперь в наших объяснениях можно перейти к многополосному американскому флагу.
Когда у нас не два, не три, а любое количество разрядов, мы фиксируем, где должен начинаться каждый разряд (его «полоса») и перераскидываем элементы по своим «полосам».
В этом алгоритме числа обычно рассматриваются не как десятичные, а в другой разрядности, чаще всего являющейся степенью двойки. Зачастую в качестве основания для разрядности берётся число 256 (несколько реже 128), что позволяет эффективно адаптировать сортировку для упорядочивания строк. Для чисел для разрядности удобнее брать небольшие 2n (2, 4, 16 и т.д), что позволяет сравнивать путём сдвига по битам, вместо возведения в степень при сравнении десятичных чисел.
В анимации показано на примере разрядности с основанием 16:
В статье про подсчётные сортировки с приблизительным распределением [4] есть визуально очень похожий алгоритм — сортировка аппроксимацией. Там мы подсчитывали сколько раз встречалось каждое число в массиве — и перераспределяли элементы в соответствии с полученными локализациями. Здесь считаем сколько раз встречается каждая цифра в разряде для элементов подмасива — и тоже перераспределяем элементы в подмассиве в соответствии с полученными локализациями. Если аппроксимация — разновидность сортировки подсчётом, то «американка» — это подсчётно-разрядная сортировка.
# Для числа определяем какая цифра в указанном разряде принятой разрядности
def get_radix_val(x, digit, radix) -> int:
return int(floor(x / radix**digit)) % radix
# Для каждой цифры в разряде определяем локализацию для данного разряда принятой разрядности
def compute_offsets(a_list, start: int, end: int, digit, radix) -> list:
# Подготовка пустого массива для количеств встретившихся цифр в разряде
counts = [0 for _ in range(radix)]
for i in range(start, end): # Перебираем элементы подмассива на данном уровне рекурсии
# Какая цифра в разряде у этого элемента массива
val = get_radix_val(a_list[i], digit, radix)
counts[val] += 1 # Подсчёт количеств встретившихся цифр в разряде
# Подготовка пустого массива для локализаций встретившихся цифр в разряде
offsets = [0 for _ in range(radix)]
sum = 0
# Зная количества для всех разрядов подсчитываем локализации разрядов
for i in range(radix):
offsets[i] = sum
sum += counts[i]
return offsets
# Обмены в подмассиве согласно локализации
def swap(a_list, offsets, start: int, end: int, digit, radix) -> None:
i = start # С какого элемента будем в цикле просматривать подмассив вправо
next_free = copy(offsets) # Копируем массив локализаций для поиска свободных мест
# Перебираем разряды (которые определяют блоки элементов массива с этими разрядами)
cur_block = 0
while cur_block < radix-1: #
if i >= start + offsets[cur_block+1]:
cur_block += 1
continue
radix_val = get_radix_val(a_list[i], digit, radix)
if radix_val == cur_block:
i += 1
continue
swap_to = next_free[radix_val]
a_list[i], a_list[swap_to] = a_list[swap_to], a_list[i]
next_free[radix_val] += 1
# Рекурсивно сортируем
def american_flag_sort_helper(a_list, start: int, end: int, digit, radix) -> None:
# Для элементов подмассива для каждой разрядной цифры определяем локализацию
offsets = compute_offsets(a_list, start, end, digit, radix)
# Обмены в подмассиве согласно локализации
swap(a_list, offsets, start, end, digit, radix)
if digit == 0: # Реурсия спустилась к последнему разряду?
return # Рекурсия завершена
# Если ещё не вышли из рекурсии
for i in range(len(offsets)-1): #Перебираем массив локализаций для чисел разряда
# Рекурсия к каждому промежутку между локализациями чисел разряда
american_flag_sort_helper(a_list, offsets[i], offsets[i+1], digit-1, radix)
# Основная процедура
def american_flag_sort(a_list, radix) -> None:
#Следим, чтобы в сортируемом массиве были только целые числа
for x in a_list:
assert(type(x) == int)
# Максимум в массиве
max_val = max(a_list)
# Максимальное количестве разрядов (берём из максимума)
max_digit = int(floor(log(max_val, radix)))
# Рекурсивно сортируем - сначала охватываем весь массив
american_flag_sort_helper(a_list, 0, len(a_list), max_digit, radix)
Немецкий программист Мальте Скарупке (Malte Skarupke) заявил о том, что разработал новый алгоритм сортировки, являющийся кардинально усовершенствованным «американским флагом» и в среднем в 2 раза обгоняющий std::sort (std::sort — алгоритм, также известный, как интроспективная сортировка — гибрид быстрой сортировки и сортировки кучей).
Судя по всему, очень эффективный алгоритм и в то же время крайне сложный — его авторская имплементация занимает почти полторы тысячи строк. Возможно, рассмотрим эту сортировку когда-нибудь, сейчас в неё углубляться не будем. Заинтересовавшиеся могут пройти по ссылкам, указанным ниже.
Dutch national flag problem [5], American flag sort [6]
Ska sort: I Wrote a Faster Sorting Algorithm (Part 1 [7], Part 2 [8]) GitHub code [9]
В Excel-приложение AlgoLab появились сортировка двухцветным флагом (сортирует нули и единицы), трёхцветным флагом (сортирует нули, единицы и двойки), сортировка американским флагом. Для сортировки «Американский флаг» можно (в комментарии к ячейке с названием алгоритма) указать систему счисления для распределения — по умолчанию используется 16-ричная.
Автор: Валерий Макаров
Источник [16]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/python/341567
Ссылки в тексте:
[1] Image: https://www.edsd.ru/
[2] портированием и миграцией программного обеспечения: https://www.edsd.ru/ru/uslugi/portirovanie-i-migracija
[3] разработкой мобильных приложений Android и iOS: https://www.edsd.ru/ru/proekty/mobilnye_prilozhenija
[4] подсчётные сортировки с приблизительным распределением: https://habr.com/ru/post/478654/
[5] Dutch national flag problem: https://en.wikipedia.org/wiki/Dutch_national_flag_problem
[6] American flag sort: https://en.wikipedia.org/wiki/American_flag_sort
[7] Part 1: https://probablydance.com/2016/12/27/i-wrote-a-faster-sorting-algorithm/
[8] Part 2: https://probablydance.com/2017/01/17/faster-sorting-algorithm-part-2/
[9] GitHub code: https://github.com/skarupke/ska_sort/
[10] Excel-приложение AlgoLab.xlsm: https://habr.com/post/414447/
[11] Сортировки обменами: https://habr.com/post/414653/
[12] Сортировки вставками: https://habr.com/post/415935/
[13] Сортировки выбором: https://habr.com/post/422085/
[14] Сортировки слиянием: https://habr.com/ru/post/431964/
[15] Сортировки распределением: https://habr.com/ru/post/472466/
[16] Источник: https://habr.com/ru/post/481304/?utm_source=habrahabr&utm_medium=rss&utm_campaign=481304
Нажмите здесь для печати.