сорт американского флага
 | Эта статья нуждается в дополнительных цитатах для проверки . ( июль 2017 г. ) |
Сортировка по американскому флагу — это эффективный на месте вариант поразрядной сортировки , который распределяет элементы по сегментам. Алгоритмы несравнительной сортировки, такие как поразрядная сортировка и сортировка по американскому флагу, обычно используются для сортировки больших объектов, таких как строки, для которых сравнение не является операцией за единицу времени. [1] Сортировка по американскому флагу перебирает биты объектов, рассматривая одновременно несколько битов каждого объекта. Для каждого набора битов сортировка по американскому флагу делает два прохода по массиву объектов: сначала для подсчета количества объектов, которые попадут в каждую корзину, а затем для помещения каждого объекта в свою корзину. Это особенно хорошо работает при побайтной сортировке с использованием 256 сегментов. С некоторыми оптимизациями она работает в два раза быстрее, чем быстрая сортировка для больших наборов строк . [1]
Название «Сортировка американского флага» происходит по аналогии с проблемой голландского национального флага на последнем этапе: эффективно разделить массив на множество «полос».
Алгоритм
[ редактировать ] | Эта статья может сбивать с толку или быть непонятной читателям . В частности, выше упоминалось, что (1) сортировка американским флагом обычно используется для сортировки больших объектов, таких как строки, и (2) сортировка американским флагом в два раза быстрее, чем быстрая сортировка для больших наборов строк; однако в этом разделе говорится, что сортировка по американскому флагу может сортировать только целые числа. Дополнительное уточнение «или объекты, которые можно интерпретировать как целые числа» совершенно бессмысленно, поскольку каждый мыслимый объект в памяти компьютера можно интерпретировать как целое число. ( Октябрь 2020 г. ) |
Алгоритмы сортировки обычно сортируют список объектов в соответствии с некоторой схемой упорядочения. В отличие от алгоритмов сортировки на основе сравнения , таких как быстрая сортировка , сортировка по американскому флагу основана на прямом сравнении байтов (числовом представлении) базовых объектов. Алгоритмы сортировки на месте, включая сортировку по американскому флагу, выполняются без выделения значительного объема памяти сверх того, который используется исходным массивом. Это значительное преимущество как в плане экономии памяти, так и во времени при копировании массива.
Сортировка по американскому флагу работает путем последовательного разделения списка объектов на сегменты на основе первой цифры их представления по основанию N (используемая база называется системой счисления ). Когда N равно 3, каждый объект можно переместить в правильную корзину с помощью алгоритма национального флага Нидерландов . Однако когда N больше, объекты не могут быть немедленно переставлены на места, поскольку неизвестно, где должен начинаться и заканчиваться каждый сегмент. Сортировка по американскому флагу позволяет обойти эту проблему, выполняя два прохода по массиву. Первый проход подсчитывает количество объектов, принадлежащих каждому из N сегментов. Начало каждого сегмента затем вычисляется как сумма размеров предыдущих сегментов. Второй проход помещает каждый объект в правильную корзину.
Сортировка по американскому флагу наиболее эффективна при системе счисления, равной степени 2, поскольку можно использовать операции сдвига битов вместо дорогостоящего возведения в степень для вычисления значения каждой цифры . При сортировке строк с использованием 8- или 7-битных кодировок, таких как ASCII , обычно используется система счисления 256 или 128, что соответствует посимвольной сортировке. [1]
Вопросы производительности
[ редактировать ]Стоит отметить, что для текста на чистом английском алфавите гистограмма счетчиков всегда разрежена. В зависимости от оборудования, возможно, стоит очистить счетчики при заполнении корзины (как в исходной статье); или, возможно, стоит поддерживать максимальный и минимальный активный сегмент или более сложную структуру данных, подходящую для разреженных массивов. Также важно использовать более простой метод сортировки для очень маленьких наборов данных, за исключением патологических случаев, когда ключи могут иметь очень длинные префиксы.
Самое главное, что этот алгоритм следует случайной перестановке и поэтому особенно недружелюбен к кэшу для больших наборов данных. [2] [ источник, созданный пользователем ] Это подходящий алгоритм в сочетании с k алгоритмом слияния -way . [ нужна ссылка ] (Оригинальная статья была написана до того, как кэш-память стала широко использоваться.)
Псевдокод
[ редактировать ]american_flag_sort(Array, Radix)
for each digit D:
# first pass: compute counts
Counts <- zeros(Radix)
for object X in Array:
Counts[digit D of object X in base Radix] += 1
# compute bucket offsets
Offsets <- [ sum(Counts[0..i]) for i in 1..Radix]
# swap objects into place
for object X in Array:
swap X to the bucket starting at Offsets[digit D of X in base Radix]
for each Bucket:
american_flag_sort(Bucket, Radix)
Пример реализации на Python
[ редактировать ]Этот пример, написанный на языке программирования Python, будет выполнять сортировку по американскому флагу для любого основания счисления, равного 2 или больше. Простота изложения предпочтительнее умного программирования, поэтому вместо методов сдвига битов используется функция журнала.
from math import floor, log
from copy import copy
def get_radix_val(x, digit, radix):
return int(floor(x / radix**digit)) % radix
def compute_offsets(a_list, start, end, digit, radix):
counts = [0 for _ in range(radix)]
for i in range(start, end):
val = get_radix_val(a_list[i], digit, radix)
counts[val] += 1
offset = start
offsets = [start]
for i in range(radix):
offset += counts[i]
offsets.append(offset)
return offsets
def swap(a_list, offsets, start, end, digit, radix):
next_free = copy(offsets)
cur_block = 0
while cur_block < radix:
i = next_free[cur_block]
if i >= offsets[cur_block+1]:
cur_block += 1
continue
radix_val = get_radix_val(a_list[i], digit, radix)
if radix_val != cur_block:
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, end, digit, radix):
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):
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)
См. также
[ редактировать ]- Сортировка ведром
- Быстрая сортировка с несколькими ключами
- Поразрядная сортировка
- Проблема с национальным флагом Нидерландов
Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б с Макилрой, Питер М.; Бостик, Кейт; Макилрой, М. Дуглас (1993). «Инженерная поразрядная сортировка» (PDF) . Вычислительные системы . 6 (1): 5–27.
- ^ «Алгоритм — поразрядная сортировка на месте» . Переполнение стека . Проверено 18 октября 2020 г.
Общий
[ редактировать ]
В этой статье использованы общедоступные материалы из Пол Э. Блэк. «Сортировка американского флага» . Словарь алгоритмов и структур данных . НИСТ .
