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

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

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

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

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

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

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

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

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

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

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

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

Линейный выбор с обменом: использование обменов

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

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

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

По окончании первого просмотра запись, ключ которой расположен в рабочей памяти, переставляется с записью из вершины списка. Теперь наименьш