29.12.2019 22:58
valemak 3 8700 Источник

Чтобы понять принцип действия этой «многополосной» сортировки проще для начала разобраться на примере флага с тремя полосами. А чтобы легко разобраться с трёхцветным флагом, лучше сначала посмотреть, как это работает на примере двухцветного. А чтобы разобраться с двухцветным...
EDISON Software - web-development
Статья написана при поддержке компании EDISON.

Мы занимаемся портированием и миграцией программного обеспечения, а также разработкой мобильных приложений Android и iOS.

Мы очень любим теорию алгоритмов! ;-)

Двухцветный флаг



Для начала рассмотрим случай, когда числа в сортируемом массиве распределяются всего по двум разрядам. Для простоты примем, что у нас массив, состоящий из нулей (младший разряд) и единиц (старший разряд).

Таким образом у нас всего две «полосы»: в одну мы будем перемещать младшие разряды (нули), а в другую старшие разряды (единицы). Для демонстрации пойдёт любой двухцветный флаг. Например, флаг Украины.



Что тут происходит? Так как на первом этапе неизвестно, сколько у нас нулей и сколько единиц, поэтому непонятно, каких размеров в итоге окажется каждая из «полос». Поэтому ставим на ключи массива два указателя. Для младшего разряда указатель установлен на начало массива, для старшего — в конец. Затем делаем однократный проход по массиву слева-направо и смотрим каждый разряд-элемент.

Если при проходе элемент равен старшему разряду, то второй указатель нам подсказывает, куда нужно перенести этот элемент (производим обмен). Указатель для вставки следующего элемента перемещается влево, «полоса» для старшего разряда расширилась.

Если он равен младшему разряду, то указатель для него перемещаем на один элемент вправо. Так как у нас всего два разряда, перенесить элемент не приходится, он уже на своём месте. «Полоса» для младшего разряда естественным образом стала шире.

В итоге два указателя, движущихся навстречу друг другу, столкнутся в одной точке, а разряды будут упорядочены в своих «полосах». При этом не понадобится проход по всему массиву — когда произойдёт встреча указателей где-то в середине, алгоритм выполнит свою работу.

Задача национального голландского флага :: Dutch national flag problem



Слегка усложним задачу, рассмотрим не два разряда, а три. Пусть у нас элементы массива относятся к младшему (нули), среднему (единицы) и старшему (двойки) разрядам.

Для демонстрации возьмём трёхполосный красно-бело-синий флаг Франции Люксембурга России Шлезвиг-Гольдштейна Нидерландов. Почему именно флаг Нидерландов? Потому что Эдсгер Дейкстра в своих лекциях именно на примере этого флага рассмотрел соответствующий алгоритм, который был назван как «задача голландского национального флага».



Как видите, тут ничего особо нового. Для каждого разряда свой указатель. Изначально метки для младшего и среднего занимают стартовые позиции в начале массива и перемещаются вправо, когда встречается соответствующий элемент. Указатель для старшего разряда сначала находится в конце массива и движется влево.

Проход по массиву также по факту будет неполный, если разряды распределены более-менее равномерно, то алгоритм пройдёт 2/3 массива, прежде чем раскидает все элементы по своим «полосам».

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



Теперь в наших объяснениях можно перейти к многополосному американскому флагу.

Когда у нас не два, не три, а любое количество разрядов, мы фиксируем, где должен начинаться каждый разряд (его «полоса») и перераскидываем элементы по своим «полосам».

В этом алгоритме числа обычно рассматриваются не как десятичные, а в другой разрядности, чаще всего являющейся степенью двойки. Зачастую в качестве основания для разрядности берётся число 256 (несколько реже 128), что позволяет эффективно адаптировать сортировку для упорядочивания строк. Для чисел для разрядности удобнее брать небольшие 2n (2, 4, 16 и т.д), что позволяет сравнивать путём сдвига по битам, вместо возведения в степень при сравнении десятичных чисел.

В анимации показано на примере разрядности с основанием 16:



  1. При первом проходе — поиск максимума с целью определить максимальное количество разрядов среди элементов в массиве (для того чтобы корректно извлекать определённые по счёту разряды из элементов).
  2. Затем происходит рекурсивная обработка. При вызове указываются границы подмассива и текущий обрабатываемый разряд. На первом вызове подмассивом является весь массив, берётся самый первый разряд слева.
  3. Среди элементов подмассива осуществляется начальный подсчёт — сколько раз каждая цифра встречается в текущем разряде. Этот посдчёт позволяет определить локализации для этих цифр разрядов (т.е. известны пределы и местонахождение «полосы», в которую нужно переместить те элементы, которые имеют очередную цифру в определённом разряде). Собственно, локализации — это указатели на «полосы», куда нужно перемещать соответствующие элементы.
  4. В соответствии с локализациями-указателями происходит обмен на месте — по цифре в разряде видно, куда нужно отправить элемент, на его место приходит другой элемент, с которым произошёл обмен. Этот пункт выполняется до тех пор, пока при очередном обмене пришедший из другого места элемент не окажется на своём месте (тогда можно переходить к следующему элементу подмассива и аналогично для него выполнить этот пункт).
  5. После того, как в результате обменов перераспределили элементы в блоки по цифрам в очередном разряде, происходит рекурсия — к каждому блоку как к подмассиву применяется этот же алгоритм, в качестве текущего разряда берётся следующий по счёту.

В статье про подсчётные сортировки с приблизительным распределением есть визуально очень похожий алгоритм — сортировка аппроксимацией. Там мы подсчитывали сколько раз встречалось каждое число в массиве — и перераспределяли элементы в соответствии с полученными локализациями. Здесь считаем сколько раз встречается каждая цифра в разряде для элементов подмасива — и тоже перераспределяем элементы в подмассиве в соответствии с полученными локализациями. Если аппроксимация — разновидность сортировки подсчётом, то «американка» — это подсчётно-разрядная сортировка.

Сортировка «Американский флаг» - реализация на Python
# Для числа определяем какая цифра в указанном разряде принятой разрядности
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)

Ска-сортировка :: Ska sort


Немецкий программист Мальте Скарупке (Malte Skarupke) заявил о том, что разработал новый алгоритм сортировки, являющийся кардинально усовершенствованным «американским флагом» и в среднем в 2 раза обгоняющий std::sort (std::sort — алгоритм, также известный, как интроспективная сортировка — гибрид быстрой сортировки и сортировки кучей).

  1. Массив сортируется рекурсивно, на первом уровне рекурсии в качестве подмассива берётся весь массив.
  2. Если в подмассиве менее 128 элементов, то для него вызывается std::sort.
  3. Если в подмассиве от 128 до 1024 элементов, то для него вызывается сортировка «Американский флаг».
  4. Если в подмассиве более 1024 элементов, то для него вызывается ска-сортировка.
  5. Также, во избежания худшего случая, если слишком большая рекурсивная вложенность (более 16-ти уровней), алгоритм переключается на std::sort, даже если в подмассиве более 128 элементов.

Судя по всему, очень эффективный алгоритм и в то же время крайне сложный — его авторская имплементация занимает почти полторы тысячи строк. Возможно, рассмотрим эту сортировку когда-нибудь, сейчас в неё углубляться не будем. Заинтересовавшиеся могут пройти по ссылкам, указанным ниже.

Ссылки


Dutch national flag problem, American flag sort

Ska sort: I Wrote a Faster Sorting Algorithm (Part 1, Part 2) GitHub code

Статьи серии:


В Excel-приложение AlgoLab появились сортировка двухцветным флагом (сортирует нули и единицы), трёхцветным флагом (сортирует нули, единицы и двойки), сортировка американским флагом. Для сортировки «Американский флаг» можно (в комментарии к ячейке с названием алгоритма) указать систему счисления для распределения — по умолчанию используется 16-ричная.

Комментарии (3)


  1. dmrt
    30.12.2019 16:20
    #21078496
    +1

    Это был тяжелый год,
    Был он тяжелей, чем тот


  1. a5b
    01.01.2020 23:38
    #21084078
    +2

    Подскажите, где в Кнуте TAOCP описаны эти и подобные вариации radix sort?
    (American flag sort… is an efficient, in-place variant of radix sort)


    1. valemak Автор
      02.01.2020 00:00
      #21084096
      +2

      Кнут не очень углублялся в поразрядные сортировки. В третьем томе в главе 5.2.2 всего 5 страниц уделяется поразрядному способу. Там у него поразрядная сортировка по младшим разрядам. Сортировка «Американский флаг» сортирует по старшим разрядам, так что дополнительной информации к этой статье у Кнута Вы не найдёте :-)