WikiDer > Сортировка турнира
Эта статья нужны дополнительные цитаты для проверка. (Июль 2012 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
Учебный класс | Алгоритм сортировки |
---|---|
Структура данных | Множество |
Худший случай спектакль | 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]
Рекомендации
- ^ Дональд Кнут, Искусство программирования, Сортировка и поиск, Том 3, 1973 год. Аргумент "снегоочистителя". п. 254
- ^ Степанов, Александр; Кершенбаум, Аарон (1986). Использование турнирных деревьев для сортировки (PDF) (Технический отчет). Бруклин: Центр передовых технологий в области телекоммуникаций, Политехнический университет. C.A.T.T. Технический отчет 86-13.
- Кершенбаум и др., 1988 г., "Императивное программирование высшего порядка"