Lucky Radix – Arc.Ask3.Ru

Оглавление1 Сортировка по основанию1.1 История и применение1.2 Порядок цифр1.3 Сложность и производительность1.4 Специализированные варианты1.5 Применение к параллельным вычислениям1.6 Параллельные алгоритмы […]

Сортировка по основанию

  • История и применение

    • Сортировка по основанию была предложена Германом Холлеритом в 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 – Счетная сортировка и сортировка по основанию, Пэт Морин.  

Полный текст статьи:

Lucky Radix – Arc.Ask3.Ru

Оставьте комментарий

Прокрутить вверх