Оглавление
- 1 Сортировка по основанию
- 1.1 История и применение
- 1.2 Порядок цифр
- 1.3 Сложность и производительность
- 1.4 Специализированные варианты
- 1.5 Применение к параллельным вычислениям
- 1.6 Параллельные алгоритмы сортировки
- 1.7 Сортировки PRAM
- 1.8 Древовидная сортировка по основанию
- 1.9 Другие виды сортировки
- 1.10 Рекомендации и внешние ссылки
- 1.11 Полный текст статьи:
- 2 Lucky Radix – Arc.Ask3.Ru
Сортировка по основанию
-
История и применение
- Сортировка по основанию была предложена Германом Холлеритом в 1887 году.
- В 1954 году Гарольд Х. Сьюард разработал первый экономичный алгоритм для сортировки по основанию.
- Сортировка по основанию применяется к данным, которые можно отсортировать лексикографически.
-
Порядок цифр
- Сортировка может начинаться с самой значимой цифры (MSD) или наименее значимой цифры (LSD).
- LSD сортирует короткие ключи перед длинными, а затем сортирует ключи одинаковой длины лексикографически.
- MSD сортирует строки или целочисленные представления фиксированной длины, расширяя короткие ключи до размера самого большого ключа.
-
Сложность и производительность
- Сортировка по основанию выполняется в O(n⋅w) время, где n — количество ключей, а w — длина ключа.
- LSD может достигать нижней границы для w при разделении ключей переменной длины на группы.
- Оптимизированная сортировка по основанию может быть очень быстрой при работе в подходящей области.
-
Специализированные варианты
- Двоичная сортировка по основанию MSD может быть реализована на месте.
- Стабильные реализации сортировки по основанию MSD требуют использования буфера памяти.
- Гибридные подходы включают использование сортировки вставкой для ускорения сортировки по основанию.
-
Применение к параллельным вычислениям
- Сортировка по основанию особенно применима для параллельных вычислений.
- Каждая ячейка может быть отсортирована независимо, что позволяет использовать несколько процессоров.
- На верхнем уровне рекурсии параллелизм заложен в вычислительной части алгоритма.
-
Параллельные алгоритмы сортировки
- При случайном вводе данных все ячейки заполняются почти одинаково, что обеспечивает параллелизм.
- Алгоритмы трех венгров и Ричарда Коула имеют сложность O(log(n)).
- Сортировка битоновым слиянием Батчера имеет сложность O(log2(n)).
-
Сортировки PRAM
- Самые быстрые сортировки PRAM описаны Дэвидом М.У. Пауэрсом в 1991 году.
- Распараллеленная быстрая сортировка выполняется за O(log(n)) на CRCW-PRAM.
- Radixsort работает за O(k), где k – максимальная длина клавиши.
-
Древовидная сортировка по основанию
- Сортировка по основанию может быть выполнена путем построения дерева из входного набора.
- Это полезно для определенных типов данных, таких как burstsort.
-
Другие виды сортировки
- Сортировщики карточек IBM серии 80.
- Сортировка по Киркпатрику-Райшу.
- Сумма префикса.
-
Рекомендации и внешние ссылки
- Объяснение, псевдокод и реализация на C и Java.
- Высокопроизводительная реализация LSD-сортировки по основанию в JavaScript.
- Высокопроизводительная реализация радикальной сортировки LSD и MSD на C# с исходным кодом на GitHub.
- Видеоурок по сортировке MSD по основанию.
- Демонстрация и сравнение радикальной сортировки с пузырьковой сортировкой, сортировкой слиянием и быстрой сортировкой, реализованными на JavaScript.
- Статья о радикальной сортировке чисел IEEE с плавающей запятой с реализацией.
- Более быстрая сортировка с плавающей запятой и множественное гистограммирование благодаря реализации на C++.
- Указатели на визуализации сортировки по основанию.
- Библиотека USort, архивированная 7 августа 2011 года на Wayback Machine.
- Дональд Кнут. “Искусство компьютерного программирования”, Том 3: Сортировка и поиск, Третье издание.
- Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест и Клиффорд Стайн. Введение в алгоритмы, Второе издание.
- Исходный код BRADSORT версии 1.50, автор Эдвард Ли.
- Эффективная сортировка больших наборов строк на основе Trie, авторы Ранджан Синха и Джастин Зобел.
- Открытые структуры данных – Java Edition – Раздел 11.2 – Счетная сортировка и сортировка по основанию, Пэт Морин.
- Открытые структуры данных – Редакция C++ – Раздел 11.2 – Счетная сортировка и сортировка по основанию, Пэт Морин.