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

Основные понятия и методы сортировки

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

Записи, поля и ключи. Единица данных, типично обрабатываемая информационными системами, называется записью. Запись – это совокупность элементов информации о каком-то событии или структуре. Каждый элемент информации в записи, такой как номер служащего, цена единицы товара или валовой объем, называется полем записи. Совокупность полей идентифицирует и описывает то, что представлено в записи. Из записей составляются файлы или наборы данных. Сортировка является процессом перестановки записей или их индексов, при котором их взаимное расположение в файле приводиться в порядок, определяемый некоторым известным ключом. Ключом называется поле, содержащее величину, используемую в правилах упорядочивания файла.

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

Определить, какой ключ «меньше», можно, используя любое правило. Очевидными правилами являются: алфавитное упорядочивание, числовое и буквенно-цифровое. (В последнем правиле ключи могут содержать смесь букв и цифр; соглашения, принятые в системе, определяют упорядочение букв и цифр.)

Ключом записи может быть одно поле или комбинация полей, распределенных по записи. Если ключ состоит из нескольких несоприкасающихся полей, то он называется составным ключом.

Иногда желательно упорядочение внутри упорядочивания. Например, файл может быть упорядочен по номеру места работы, а внутри этого упорядочения – по номеру служащего. Поле, содержащее номер места работы, называется старшим ключом, а поле, содержащее номер служащего, – младшим ключом. Так модно определить несколько уровней ключей, и все уровни, отличные от первого, называются младшими ключами. Старший и младший ключи можно рассматривать как один составной ключ в записи.

В информационной системе иногда удобно, чтобы файлы упорядочивались не единственным способом. Различные сортировки в качестве ключа могут использовать различные поля.

Запись может состоять только из поля ключа. В обработке научных приложений это не является чем-то исключительным. В данной работе при рассмотрении методов сортировки будет предполагаться, что записи состоят из одного поля. Это сделано для того, чтобы упростить первоначальное представление о методах сортировки за счет устранения побочных проблем, возникающих при перемещении данных. Поскольку эти методы одинаково хорошо применимы к записям, содержащим как ключевые, так и неключевые поля, то это предположение не ограничивает общности.

Традиционно методы сортировки делят на внутренние и внешние. Внутренние методы – это такие методы, которые могут применяться с приемлемой производительностью только к тем спискам данных, которые целиком помещаются в основной (оперативной) памяти процессора. ............