Сортировка турнира - Tournament sort

Сортировка турнира
Учебный классАлгоритм сортировки
Структура данныхМножество
Худший случай спектакльO (п бревно п)
Средний спектакльO (п бревно п)

Сортировка турнира это алгоритм сортировки. Он улучшает наивность сортировка выбора используя приоритетная очередь чтобы найти следующий элемент сортировки. При сортировке наивным выбором требуется О (п) операции для выбора следующего элемента п элементы; в турнирной сортировке требуется O (logп) операций (после построения начального турнира за O (п)). Сортировка турниров - это разновидность heapsort.

Обычное приложение

Сортировки выбора замены в турнирах используются для сбора начальных прогонов для внешних алгоритмов сортировки. По идее, внешний файл читается, и его элементы помещаются в приоритетную очередь до тех пор, пока она не заполнится. Затем минимальный элемент извлекается из очереди и записывается как часть первого запуска. Следующий элемент ввода считывается и помещается в очередь, а min снова выбирается и добавляется к запуску. Есть небольшая хитрость: если новый элемент, помещаемый в очередь, меньше, чем последний элемент, добавленный к запуску, тогда значение сортировки элемента увеличивается, поэтому он будет частью следующего запуска. В среднем цикл будет на 100% длиннее, чем емкость очереди с приоритетом.[1]

Сорта турниров также могут использоваться в N-сторонних объединениях.

Этимология

Название происходит от его сходства с турнир на выбывание где много игроков (или команд) играют в двусторонние матчи. В каждом матче сравниваются игроки, и победивший игрок продвигается к игре на следующем уровне. Иерархия продолжается до тех пор, пока в финальном матче не будет определен окончательный победитель. Турнир определяет лучшего игрока, но игрок, проигравший в финальном матче, не может быть вторым лучшим - он может уступать другим игрокам, победившим победителя.

Выполнение

Ниже представлена ​​реализация сортировки турниров в Haskell, на основе Схема код Степанова и Кершенбаума.[2]

импорт Данные.Дерево- | По материалам «TOURNAMENT-SORT!» Из доклада Степанова и Кершенбаума.турнирSort :: Ord т       => [т]  - ^ Ввод: несортированный список       -> [т]  - ^ Результат: отсортированная версия вводатурнирSort список        = идти (чистый<$>список) - сначала оберните каждый элемент как лес из одного дерева куда идти [] = []       идти деревья = (rootLabel победитель) : (идти (сублес победитель))        куда победитель = playTournament деревья- | По материалам «ТУРНИР!» В отчете Степанова и КершенбаумаplayTournament :: Ord т         => лес т - ^ Входной лес         -> Дерево т   - ^ Последнее продвинутое дерево во входных данныхplayTournament [дерево] = деревоplayTournament деревья = playTournament (playRound деревья [])- | По материалам доклада Степанова и Кершенбаума «ТУРНИР-РАУНД!»playRound :: Ord т       => лес т - ^ Лес деревьев, которые еще не участвовали в раунде       -> лес т - ^ Лес деревьев, выигравших в раунде       -> лес т - ^ Вывод: лес, содержащий продвинутые версии                   - деревьев, выигравших свои игрыplayRound [] сделано = сделаноplayRound [дерево] сделано = дерево:сделаноplayRound (дерево0:дерево1:деревья) сделано = playRound деревья (победитель:сделано) куда победитель = играть в игру дерево0 дерево1- | По материалам доклада Степанова и Кершенбаума «ТУРНИР-ИГРА!»играть в игру :: Ord т         => Дерево т  - ^ Ввод: ...         -> Дерево т  - ^ ... два дерева         -> Дерево т  - ^ Результат: `продвинуть победителя проигравшего`, где` победитель`                    - дерево с * меньшим * корнем из двух входовиграть в игру дерево1 дерево2    | rootLabel дерево1 <= rootLabel дерево2  = продвигать дерево1 дерево2    | иначе                           = продвигать дерево2 дерево1- | По материалам доклада Степанова и Кершенбаума «GRAB!»продвигать :: Дерево т  - ^ `Победитель`        -> Дерево т  - ^ `Проигравший`        -> Дерево т  - ^ Результат: дерево, корень которого является корнем победителя.                   - и чьи дети:                   - * `неудачник`,                   - * все дочерние элементы из `Winner`продвигать победитель неудачник = Узел {    rootLabel = rootLabel победитель,    сублес = неудачник : сублес победитель}главный :: IO ()главный = Распечатать $ турнирSort testList куда testList = [0, 1, 2, 3, 4, 5]

Рекомендации

  1. ^ Дональд Кнут, Искусство программирования, Сортировка и поиск, Том 3, 1973 год. Аргумент "снегоочистителя". п. 254
  2. ^ Степанов, Александр; Кершенбаум, Аарон (1986). Использование турнирных деревьев для сортировки (PDF) (Технический отчет). Бруклин: Центр передовых технологий в области телекоммуникаций, Политехнический университет. C.A.T.T. Технический отчет 86-13.