Организация данных и структуры данных
Метод обменной сортировки с выбором Метод турнирной сортировки Методом квадратичной сортировки Метод вставки Методы Замещения Слияние рассортированных подфайлов Осциллирующей сортировки Многофазная сортировка Сравнение методов внешней сортировки Генераторы программ сортировки слияния Информация и ее представление в вычислительных машинах Ассоциативная структура Последовательная структура Связанный список Простые операции над списками Иерархические структуры Древовидная структура Линейное представление древовидной структуры Преобразование арифметических выражений в списковые структуры Сетевая структура Системы управления базами данных Инвертированные файлы Пример инвертированного файла Поиск по нескольким ключам Элементы системы управления базой данных Работа системы управления базой данных Роль администратора базы данных Определения Организация в записи Компоненты записи Блоки Форматы блоков и записей Организация и методы доступа Последовательная организация Метод доступа с очередями Библиотечная организация Оглавление тома Метки оглавления тома Метки тома магнитной ленты Прямая организация Прямая адресация Методы рандомизации Сравнение методов рандомизации Индексно-последовательная организация Область основных данных Области переполнения Области индексов Произвольный поиск Режимы обработки Добавление новых записей Статистика Общее про методы сортировки Сортировка в основной памяти Метод сортировки посредством выбора |
Методы ЗамещенияЭффективность сортировки больших объемов данных можно значительно повысить, используя так называемые методы замещения. Согласно этим методам, наименьший элемент, имеющий наименьший ключ) при каждом просмотре замещается неким новым элементом из несортированной части файла. Если ключ нового элемента меньше, чем ключ замещенного им элемента, только что переданного в рассортированный файл, то он маркируется, и эта маркировка учитывается при последующих сравнениях так, как если бы ключ имел значение щах. Когда маркированными окажутся ключи всех элементов, то все признаки маркировки уничтожаются. Готова очередная рассортированная элементарная или единичная строка, и начинается формирование новой строки. Принцип метода выборочного замещения показан на рис. 9.18.
В табл. 9.1 приведены характеристики (количество необходимых сравнений для п элементов) различных методов сортировки. Конечно, эта характеристика сама по себе не свидетельствует об эффективности того или иного метода. Необходимо также учитывать и другие операции, которые должны выполняться при сортировке, требуемый объем памяти, а также применимость методики замещения. Элементарные строки, вырабатываемые после каждого этапа внутренней сортировки, будут длиннее, если использовать методику замещения. Это уменьшает количество операций ввода-вывода на этапе слияния, а также позволяет значительно уменьшить время сортировки. |
|||||||||||||||||||||