Метод вставки

Другой метод — метод вставки состоит в том, что поочередно выбираемые элементы сортируемого файла заносятся в «как бы» рассортированный файл, причем элемент, выбранный первым, помещается в середину рассортированного файла. Путем перемещения больших элементов вниз или меньших вверх на одну позицию каждый вновь выбранный элемент вставляют в соответствующее ему место среди ранее выбранных элементов.

Наиболее быстрой является сортировка, основанная на непосредственном вычислении с помощью соответствующего алгоритма места рассматриваемого элемента в рассортированном файле. Примерами такого подхода являются методы хеширования, обсуждавшиеся в разд. 5.4.6, 5.4.7 и 9.3. Эти методы можно использовать только в случаях размещения данных в основной памяти или на устройствах прямого доступа. Главный недостаток этих методов заключается в том, что эффективность алгоритма очень сильно зависит от характера распределения ключей, и поэтому он должен выбираться применительно к каждому конкретному случаю, а не является общим. Программы сортировки, поставляемые изготовителями машин, должны быть эффективными для различных типов распределения ключей данных. В связи с этим такие методы используются только специализированными подпрограммами сортировки.


Организация данных и структуры данных Метод обменной сортировки с выбором Метод турнирной сортировки Методом квадратичной сортировки Метод вставки Методы Замещения Слияние рассортированных подфайлов Осциллирующей сортировки Многофазная сортировка Сравнение методов внешней сортировки Генераторы программ сортировки слияния Информация и ее представление в вычислительных машинах Ассоциативная структура Последовательная структура Связанный список Простые операции над списками Иерархические структуры Древовидная структура Линейное представление древовидной структуры Преобразование арифметических выражений в списковые структуры Сетевая структура Системы управления базами данных Инвертированные файлы Пример инвертированного файла Поиск по нескольким ключам Элементы системы управления базой данных Работа системы управления базой данных Роль администратора базы данных Определения Организация в записи Компоненты записи Блоки Форматы блоков и записей Организация и методы доступа Последовательная организация Метод доступа с очередями Библиотечная организация Оглавление тома Метки оглавления тома Метки тома магнитной ленты Прямая организация Прямая адресация Методы рандомизации Сравнение методов рандомизации Индексно-последовательная организация Область основных данных Области переполнения Области индексов Произвольный поиск Режимы обработки Добавление новых записей Статистика Общее про методы сортировки Сортировка в основной памяти Метод сортировки посредством выбора	Метод вставки Другой метод — метод вставки состоит в том, что поочередно выбираемые элементы сортируемого файла заносятся в «как бы» рассортированный файл, причем элемент, выбранный первым, помещается в середину рассортированного файла. Путем перемещения больших элементов вниз или меньших вверх на одну позицию каждый вновь выбранный элемент вставляют в соответствующее ему место среди ранее выбранных элементов. Наиболее быстрой является сортировка, основанная на непосредственном вычислении с помощью соответствующего алгоритма места рассматриваемого элемента в рассортированном файле. Примерами такого подхода являются методы хеширования, обсуждавшиеся в разд. 5.4.6, 5.4.7 и 9.3. Эти методы можно использовать только в случаях размещения данных в основной памяти или на устройствах прямого доступа. Главный недостаток этих методов заключается в том, что эффективность алгоритма очень сильно зависит от характера распределения ключей, и поэтому он должен выбираться применительно к каждому конкретному случаю, а не является общим. Программы сортировки, поставляемые изготовителями машин, должны быть эффективными для различных типов распределения ключей данных. В связи с этим такие методы используются только специализированными подпрограммами сортировки.