Методы внутренней сортировки
Основные понятия и методы сортировки
Сортировка – это процесс расстановки элементов «в некотором порядке». Элементы размещаются так, чтобы, во-первых, вычисления требующие определенного порядка расположения данных, могли выполняться эффективно, во-вторых, результаты имели осмысленный вид, в третьих, последующие процессы бы пригодные исходные данные.
Записи, поля и ключи. Единица данных, типично обрабатываемая информационными системами, называется записью. Запись – это совокупность элементов информации о каком-то событии или структуре. Каждый элемент информации в записи, такой как номер служащего, цена единицы товара или валовой объем, называется полем записи. Совокупность полей идентифицирует и описывает то, что представлено в записи. Из записей составляются файлы или наборы данных. Сортировка является процессом перестановки записей или их индексов, при котором их взаимное расположение в файле приводиться в порядок, определяемый некоторым известным ключом. Ключом называется поле, содержащее величину, используемую в правилах упорядочивания файла.
В предположении, что результатом сортировки является физическое упорядочивание, сортировка двух записей в своей простейшей форме состоит из сравнения их ключевых полей и определений, которое из них «меньше». После этого записи переставляются так, что запись с «меньшим» ключом ставиться перед записью с «большим» ключом.
Определить, какой ключ «меньше», можно, используя любое правило. Очевидными правилами являются: алфавитное упорядочивание, числовое и буквенно-цифровое. (В последнем правиле ключи могут содержать смесь букв и цифр; соглашения, принятые в системе, определяют упорядочение букв и цифр.)
Ключом записи может быть одно поле или комбинация полей, распределенных по записи. Если ключ состоит из нескольких несоприкасающихся полей, то он называется составным ключом.
Иногда желательно упорядочение внутри упорядочивания. Например, файл может быть упорядочен по номеру места работы, а внутри этого упорядочения – по номеру служащего. Поле, содержащее номер места работы, называется старшим ключом, а поле, содержащее номер служащего, – младшим ключом. Так модно определить несколько уровней ключей, и все уровни, отличные от первого, называются младшими ключами. Старший и младший ключи можно рассматривать как один составной ключ в записи.
В информационной системе иногда удобно, чтобы файлы упорядочивались не единственным способом. Различные сортировки в качестве ключа могут использовать различные поля.
Запись может состоять только из поля ключа. В обработке научных приложений это не является чем-то исключительным. В данной работе при рассмотрении методов сортировки будет предполагаться, что записи состоят из одного поля. Это сделано для того, чтобы упростить первоначальное представление о методах сортировки за счет устранения побочных проблем, возникающих при перемещении данных. Поскольку эти методы одинаково хорошо применимы к записям, содержащим как ключевые, так и неключевые поля, то это предположение не ограничивает общности.
Традиционно методы сортировки делят на внутренние и внешние. Внутренние методы – это такие методы, которые могут применяться с приемлемой производительностью только к тем спискам данных, которые целиком помещаются в основной (оперативной) памяти процессора. Внешние методы – это такие методы, которые приемлемы для файлов данных, которые слишком велики, чтобы поместится в основной памяти, и поэтому должны в течение процесса сортировки располагаться на устройствах внешней памяти (лентах, дисках, барабанах). Слово список часто обозначает набор записей, расположенных в основной памяти.
Линейный выбор с обменом: использование обменов
В качестве примера обмена в процессе сортировки рассмотрим здесь минимальную по памяти версию линейного выбора. Обменом называется перестановка позиций двух записей в списке в зависимости от результата проверки их относительной величины. Если в списке встречается запись с ключом, меньшим, чем у предыдущей, то эти записи меняются местами. Производительность методов обмена зависит от сложности определения последовательности сравнений и обменов. Часто число обменов сокращают, откладывая обмен до конца каждого просмотра. Это прием, в частности, используется в методе, который будет описан ниже.
Линейный выбор с обменом. В начале первого просмотра предполагается, что первый элемент списка имеет наименьший ключ. Этот ключ вместе с адресом пересылается в рабочую память, где сравнивается со всеми линейными преемниками до тех пор, пока не встретится меньший ключ. Меньший ключ и его адрес становятся содержимым рабочей области памяти.
Сравнения продолжаются при новом содержимом рабочей памяти. Пересылка выполняется всегда, когда в списке встречается ключ, который меньше ключа в рабочей памяти. Таким образом, в рабочей памяти всегда расположен наименьший из уже просмотренных ключей. Просмотр заканчивается по достижении конца списка. До этого момента процесс идентичен простому линейному выбору. Сортировка обменом отличается следующим шагом.
По окончании первого просмотра запись, ключ которой расположен в рабочей памяти, переставляется с записью из вершины списка. Теперь наименьшая величина в списке занимает первую позицию. Второй просмотр идентичен первому с той лишь разницей, что вторым по величине считается второй ключ, так как первым стоит наименьший элемент. Первая позиция исключается из процесса. По окончании второго просмотра вторая запись с наименьшим ключом помещается во вторую позицию списка. Третий просмотр начинается сравнением ключа из третьей позиции и т.д. Эта процедура заканчивается, когда свое место занимает (N – 1) – я запись.
алгSort (аргцелN, вещ табA [1:N])
начцел i, j, k, Maxi
нц дляiотNдо 2 шаг -1
Maxi:= i;
нц дляjот 1 доi– 1
ЕслиA[j] >A[Maxi]
тоMaxi:= j;
все
ЕслиMaxi <> i
тоk:= A[i];
A[i]:= A[Maxi];
A[Maxi]:= k;
все
кц
кон
Оценим количество сравнений. При первом просмотре их N – 1, при втором – N – 2, при последнем – 1. Общее количество C = N –1 + N – 2 + …+ 1 = C = N× (N– 1)/2, то есть имеет порядок O(N2).
Линейный выбор с подсчетом
Метод сортировки с подсчетом описывается в литературе как процедура упорядочения внутреннего списка чисел. Фактически, это не метод сортировки, а технический прием, который можно использовать в различных методах для сокращения количества обменов или полного их устранения. Он является формой индексирования, в которой счетчик относительной позиции каждого элемента корректируется в течение процесса сравнения. Ниже будет описан этот технический прием применительно к линейному выбору.
Подсчет как технический прием. Память, используемая линейным выбором с подсчетом, будет включать область вывода (так же как и при линейном выборе) для хранения окончательно упорядоченного списка. Размер области вывода отвечает тем же соображениям, что и при линейном выборе. Дополнительно должна быть обеспечена память под счетчик для каждого элемента списка. В результате действий над значениями этих счетчиков образуется множество индексов позиций для элементов в упорядоченном списке. При каждом просмотре ключ сравнивается со своими линейными преемниками. Каждый раз, когда находится больший ключ, его счетчик увеличивается на единицу. Если найденный ключ меньше или равен, то увеличивается счетчик соответствующий большему из сравниваемому ключей. Следовательно, в любой момент времени счетчик элемента указывает количество ключей, о которых известно, что они меньше ключа рассматриваемого элемента.
При первом просмотре первый ключ в списке сравнивается со всеми остальными ключами. В его счетчике подсчитывается количество меньших ключей. В счетчиках больших ключей будут 1. При втором просмотре первый ключ не рассматривается. Второй ключ сравнивается с ключами всех преемников. Подсчеты фиксируются. Этот процесс продолжается N – 1 раз. На этом этапе известно относительная позиция каждого элемента. Помещая ключи в выходной список в соответствии со значениями их счетчиков, получаем упорядоченный список.
алгSort (арг целN, цел табA [1:N], рез цел таб B [1:N]);
начцелi, j, целтаб Count [1:N]
нц дляiотNдо 2 шаг -1
нц дляj от i– 1 до 1 шаг -1
ЕслиA[i] < A[j]
то Count [j]:= Count [j] + 1
иначеCount [i]:= Count [j]+1
все
кц
кц
нцдляiот 1 доN
B [Count [i] + 1]:= A[i]
кц
кон
Число сравнений равно N2/2. Выполняется (N-1) просмотров с N/2 сравнениями в среднем на каждом просмотре. Значение счетчиков изменяется столько раз, сколько раз выполняется сравнение.
Сортировка обменом
Сортировка обменом – это общий термин, используемый для описания семейства минимальных по памяти методов сортировки, которые меняют местами элементы списка, если предшествующий элемент больше последующего. Просмотр файла может протекать сверху вниз или снизу вверх или изменяться от просмотра к просмотру.
Существует ряд определенных вариантов, которые различаются последовательностями сравнений элементов списка. Во всех элементарных методах обмена элемент сравнивается со своим ближайшим соседом, а возможными перемещениями являются перемещение элемента с большим ключом на одну позицию вниз и перемещение элемента с меньшим ключом на одну позицию вверх. Парный обмен, стандартный обмен и просеивание являются тремя простыми формами сортировки обменом.
Метод парного обмена (также называемый «нечетно-четная перестановка») состоит из различного числа «нечетных» и «четных» просмотров. При нечетных просмотрах каждый элемент из нечетной позиции сравнивается со своим соседом из четной позиции и больший из них занимает большую позицию. Нисходящий просмотр списка продолжается до тех пор, пока последний нечетный элемент (N – 1) в списке не сравнивается с последним четным элементом N. Если в списке нечетное число элементов, то последний элемент не будет участвовать в сравнении. В течение каждого просмотра ведется подсчет обменов.