нач цел k, i, w

нц для k от N до N - 1

нц для i от 1 до N - k

если A[i] > A [i + 1]

то w:= A[i]

A[i]:= A [i + 1]

A [i + 1]:= w

все

кц

кц

кон

При сортировке «методом пузырька» выполняется N - 1 просмотр, причем на i - м просмотре производится N - i сравнений. Общее количесво сравнений C = N (N - 1)/2, то есть имеет порядок (N2).

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

Будем называть нисходящее сравнение первичным, а восходящее вторичным. Любое первичное сравнение может увеличить число вторичных сравнений. Если первичное сравнение охватывает позиции 6 и 7, то цепочка вторичных сравнений может иметь самое большее 5 сравнений. Этот максимум достигается, если исходный ключ из позиции 7 меньше всех ключей в списке, расположенных выше этой позиции. Фактическая длина последовательности вторичных сравнений зависит от величины двигающегося вверх элемента относительно величины каждого элемента из предшествующей упорядоченной части списка.

Сортировка заканчивается, когда первичное сравнение охватит (N + 1) - й элемент.

Сортировка вставками

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

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

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

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

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

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

Метод сортировки Шелла

Сортировка Шелла является расширением сортировки просеиванием. Последний просмотр в сортировке Шелла идентичен методу просеивания, описанному выше. Предшествующие просмотры используют тот же технический прием, но в них сравниваются и обмениваются не непосредственные соседи, а элементы отстоящие на заданное расстояние. Например, позиция 1 сравнивается с позицией 5, позиция 5 с позицией 9, 9 с 13 и т.д. Когда обнаружена инверсия, цепочка вторичных сравнений охватывает те элементы, которые входили в последовательность первичных сравнений. Например, если обнаружена инверсия между позициями 9 и 13, то возможная вторичная последовательность состоит из сравнений 5: 9 и 1: 5.

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

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

Вариант с отложенными обменами

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

Каждое первичное сравнение Ключi: ключi +шаг включает пересылку ключi +шаг во временную память. Сравнение позиции 1 с позицией 4, например, на самом деле включает пересылку из позиции 4 во временную память и сравнение ключа из временной памяти с ключом из позиции 1. Если ключi больше, он перемещается в позицию ключi +шаг. Если ключi +шаг больше, то перемещение не нужно. Пересылка во временную память позволяет эффективно освобождать позицию последующего элемента этой части.

Когда ключi больше, чем ключi +шаг, то ключi пересылается из своей позиции в «свободную» позицию, и метод начинает последовательность вторичных сравнений. Содержимое временной памяти (ключi +шаг) - это запись, поднимающаяся на верх данной части. Ключ каждой записи сравнивается с временной памятью и, если обнаружено, что он больше, пересылается вниз списка в текущую свободную позицию. Каждая пересылка освобождает позицию перемещенного элемента. Когда в списке обнаружен элемент с ключом, меньшим ключа временной памяти, содержимое временной памяти помещается в позицию списка освобожденной самой последней, т.е. в нужное место.

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

Быстрая сортировка

Метод быстрой сортировки был впервые описан Ч.А.Р. Хоаром В 1962 году. Быстрая сортировка - это общее название ряда алгоритмов, которые отражают различные подходы к получению критичного параметра, влияющего на производительность метода.

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

Этап определяет две части. Если значение основы хорошо аппроксимирует медиану списка, то эти две части будут примерно равной длины. Если основа является наихудшей возможной оценкой медианы (наибольшим или наименьшим элементом списка), то эти части будут длиной 0 и К - 1, где К - это длина исходного списка.

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

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

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

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

На первом этапе строятся две части. Одна из них используется в качестве исходной на втором этапе, вторая помещается в стек LIFO. Общее правило таково: первой обрабатывать меньшую часть, а границы большей запоминать в стеке. Второй этап порождает две части. Меньшая обрабатывается на третьем этапе, а большая перемещается в стек над большей частью, построенной на этапе 1. Процесс порождения частей, запоминания большей из них в стеке и разделения меньшей продолжается до тех пор, пока все части не сократятся до одного элемента. При возникновении одноэлементной части новая часть для стека не строится. Ожидающие части выбираются из стека и обрабатываются. Сортировка выполнена, когда стек пуст.

Обработка меньшей из двух частей гарантирует, что ожидающих частей в стеке будет не более log2N. Последовательность обработки частей совершенно произвольна и может изменяться по желанию программиста.

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

Алг QuickSort (арг цел m, t)

нач цел i, j, x, w

i:= m

j:= t

x:= div (A (m + t), 2)

нц

нц пока A[i] < x

i:=i+1

кц

нц пока A[j] > x

j:=j-1

кц

если i <= j

то

w:= A[i]

A[i]:= A[j]

A[j]:= w

i:= i+1

j:= j-1

все

кц пока i > j;

если m < j

то QuickSort (m, j);

все

если i < t

то QuickSort (i, t);

все

кон

Оценим эффективность метода. Предположим, что размер массива равен числу, являющемуся степенью двойки, и при каждом разделении элемент X находится точно в середине массива. В этом случае при первом просмотре выполняется N сравнений и массив разделяется на две части размерами N/2 сравнений и т.д. следовательно,

C = N + 2 (N / 2) + 4 (N / 4) + … + N (N / N) = (N log2N).

Внутреннее слияние

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

Алг Sl (арг цел k, m, q, цел таб A [1:N])

нач цел k, i, j, t, цел таб A [1:N]

i:= k

j:= m +1

t:= 1

нц пока (i <= m) и (j <= q)

если A[i] <= A[j] то

D[t]:= A[i]

i:= i +1

иначе

D[t]:= A[j]

j:= j +1

t:= t +1

все

кц

нц пока i = m

D[t]:= A[i]

i:= i +1

t:= t +1

нц пока j:= q

D[t]:= A[j]

j:= j +1

t:= t +1

кц

кц

нц для i от 1 до t - 1

A [k + i - 1]:= D[i]

кц

кон

Эффективность алгоритма составляет C = O (Nlog2N).

Страницы: 1, 2