Сортировка в основной памяти

Когда все элементы находятся в основной памяти, то их ключи непосредственно доступны и время доступа примерно равно времени выполнения операций сравнения. Однако если для сортировки необходимо разместить в основной . памяти весь набор данных, то количество данных, которые могут быть рассортированы, ограничивается. В этом разделе мы обсудим некоторые часто используемые методы внутренней сортировки. Примеры иллюстрируют сортировку записей только в порядке возрастания числовых значений одного ключа, однако аналогичным способом может быть проведена сортировка с использованием нескольких ключей и (или) в порядке убывания.<.p>

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

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


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