Метод турнирной сортировки

Более эффективным при внутренней сортировке является метод турнирной сортировки, но его сложнее программировать. Название этого метода объясняется той аналогией, которую он имеет с системой распределения мест в турнире с выбыванием. Элементы объединяются в пары, противопоставляются друг другу, и победитель (меньший элемент) принимает участие в следующем туре (8<16; 2<3, таким образом 8 и 2 играют дальше, см. рис. 9.17).

Здесь они снова объединяются в пары, сравниваются и победители проходят в следующий тур (2<8; 2 проходит дальше). Так продолжается до финального тура, победитель которого и считается лучшим в турнире, т. е. наименьшим элементом в файле. Его ключу присваивается значение max, и турнир повторяется снова с тем, чтобы выявить следующий элемент рассортированного файла. (Естественно, не надо опять выполнять все сравнения, а рассмотреть только те элементы, которые встречались в предыдущем турнире с его победителем.) (3<тах; 3<8; 3<12.) Затем ключу нового победителя также присваивается значение max, и такой процесс повторяется до тех пор, пока ключам всех элементов, за исключением одного, будет присвоено значение max. Этот элемент будет последним в рассортированном файле.


Организация данных и структуры данных Метод обменной сортировки с выбором Метод турнирной сортировки Методом квадратичной сортировки Метод вставки Методы Замещения Слияние рассортированных подфайлов Осциллирующей сортировки Многофазная сортировка Сравнение методов внешней сортировки Генераторы программ сортировки слияния Информация и ее представление в вычислительных машинах Ассоциативная структура Последовательная структура Связанный список Простые операции над списками Иерархические структуры Древовидная структура Линейное представление древовидной структуры Преобразование арифметических выражений в списковые структуры Сетевая структура Системы управления базами данных Инвертированные файлы Пример инвертированного файла Поиск по нескольким ключам Элементы системы управления базой данных Работа системы управления базой данных Роль администратора базы данных Определения Организация в записи Компоненты записи Блоки Форматы блоков и записей Организация и методы доступа Последовательная организация Метод доступа с очередями Библиотечная организация Оглавление тома Метки оглавления тома Метки тома магнитной ленты Прямая организация Прямая адресация Методы рандомизации Сравнение методов рандомизации Индексно-последовательная организация Область основных данных Области переполнения Области индексов Произвольный поиск Режимы обработки Добавление новых записей Статистика Общее про методы сортировки Сортировка в основной памяти Метод сортировки посредством выбора	Метод турнирной сортировки Более эффективным при внутренней сортировке является метод турнирной сортировки, но его сложнее программировать. Название этого метода объясняется той аналогией, которую он имеет с системой распределения мест в турнире с выбыванием. Элементы объединяются в пары, противопоставляются друг другу, и победитель (меньший элемент) принимает участие в следующем туре (8<16; 2<3, таким образом 8 и 2 играют дальше, см. рис. 9.17). Здесь они снова объединяются в пары, сравниваются и победители проходят в следующий тур (2<8; 2 проходит дальше). Так продолжается до финального тура, победитель которого и считается лучшим в турнире, т. е. наименьшим элементом в файле. Его ключу присваивается значение max, и турнир повторяется снова с тем, чтобы выявить следующий элемент рассортированного файла. (Естественно, не надо опять выполнять все сравнения, а рассмотреть только те элементы, которые встречались в предыдущем турнире с его победителем.) (3<тах; 3<8; 3<12.) Затем ключу нового победителя также присваивается значение max, и такой процесс повторяется до тех пор, пока ключам всех элементов, за исключением одного, будет присвоено значение max. Этот элемент будет последним в рассортированном файле.