Реферат: Методы внутренней сортировки
кон
Оценим количество сравнений. При первом просмотре их 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. Если в списке нечетное число элементов, то последний элемент не будет участвовать в сравнении. В течение каждого просмотра ведется подсчет обменов.
При четных просмотрах четные позиции сравниваются с соседними нечетными. Обмены выполняются тогда, когда надо, чтобы больший из пары занял нечетную позицию. Таким образом, ключи с большими значениями перемещаются на дно списка. При этом должно быть столько просмотров, сколько необходимо для того чтобы переместить в позицию число, наиболее удаленное от своей конечной позиции. Затем выполняется заключительный просмотр, необходимый для того, чтобы опознать упорядоченность. В течение этого просмотра счетчик обменов равен 0. Данный метод требует, по крайней мере, двух просмотров – одного нечетного и одного четного.
Метод стандартного обмена (также называемый «методом пузырька») перемещает один элемент списка в соответствующую позицию при каждом просмотре. Таким образом, при первом просмотре запись с наибольшим ключом помещается в последнюю позицию, при втором просмотре запись со следующим по величине ключом перемещается в предпоследнюю позицию и т.д. Метод может быть преобразован так, что будет размещать элементы по убыванию.
При первом просмотре первый элемент списка сравнивается со своим непосредственным преемником, и, если этот преемник меньше, они меняются местами. Теперь больший элемент, расположенный во второй позиции, сравнивается с элементом из третьей позиции. Обмен происходит, если необходимо больший из них разместить в третьей позиции. Затем позиция 3 сравнивается с позицией 4, позиция 4 с позицией 5 и т.д. когда позиция N – 1 сравнивается с позицией N, просмотр заканчивается.
Если в списке элемент k – 1 расположен раньше чем k, то при каждом сравнении (k – 1): k больший элемент попадает в позицию k. Элемент, перемещаемый вниз, считается в данный момент наибольшим в списке. Когда при сравнении обнаруживается, что k-й элемент больше, обмен не происходит. Следовательно, каждый раз сравниваются элемент, считающийся наибольшим (k – 1), и его непосредственный преемник k.