Сортировка методом прямого обмена.

Сортировка с помощью прямого обмена (пузырьковая сортировка)

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

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

Такой метод широко известен под именем "пузырьковая сортировка".

Алгоритм метода прямого обмена

for i = 2 to n

for j = n to i step -1

if a(j) < a(j - 1) then

x = a(j - 1)

a(j - 1) = a(j)

a(j) = x

endif

next j

next i

return

В нашем случае получился один проход “вхолостую”. Чтобы лишний раз не просматривать элементы, а значит проводить сравнения, затрачивая на это время, можно ввести флажок fl, который остается в значении false, если при очередном проходе не будет произведено ни одного обмена. На нижеприведенном алгоритме добавления отмечены жирным шрифтом.

fl = true

for i = 2 to n

if fl = false then return

Endif

fl = false

for j = n to i step -1

if a(j) < a(j - 1) then

fl = true

x = a(j - 1)

a(j - 1) = a(j)

a(j) = x

endif

next j

next i

return

Если массив уже отсортирован и применяется алгоритм с флажком, то достаточно всего одного прохода, и тогда получаем минимальное число сравнений

 

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

 

Эффективность алгоритма сортировки прямым обменом

Число сравнений C_max = n(n-1)/2, порядок О(n²).

Число перемещений М_max=3C_max=3n(n-1)/2, порядок О(n²).

Если массив уже отсортирован и применяется алгоритм с флажком, то достаточно всего одного прохода, и тогда получаем минимальное число сравнений

C_min = n - 1, порядок О(n),

а перемещения вообще отсутствуют

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

 

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

Относится к методам обменной сортировки. В основе лежит методика разделения ключей по отношению к выбранному.

Слева от 6 располагают все ключи с меньшими, а справа - с большими или равными 6.

Алгоритм быстрой сортировки

Sub Sort (L, R)

i = L

j = R

x = a((L + R) div 2)

repeat

while a(i) < x do

i = i + 1

endwhile

while a(j) > x do

j = j - 1

endwhile

if i <= j then

y = a(i)

a(i) = a(j)

a(j) = y

i = i + 1

j = j - 1

endif

until i > j

if L < j then

sort (L, j)

endif

if i < R then

sort (i, R)

endif

return

Sub QuickSort

Sort (1, n)

return

Из всех существующих методов сортировки Quick Sort самый эффективный.

Его эффективность имеет порядок О(n log₂ n)

 

Сортировка Шелла.

К улучшенным методам сортировки относятся:

Сортировка Шелла (сортировка с уменьшающимся шагом)

Быстрая сортировка (Quick Sort)

В 1959 году Д. Шеллом было предложено усовершенствование сортировки с помощью метода прямого включения. Иллюстрация его сортировки с начальным шагом, равным 4, представлена на нижеследующем рисунке.

Сначала отдельно группируются и в группах сортируются элементы, отстоящие друг от друга на расстоянии 4. Такой процесс называется четверной сортировкой. В нашем примере 8 элементов, и каждая группа состоит из двух элементов, то есть 1-й и 5-й элементы, 2-й и 6-й, 3-й и 7-й и, наконец, 4-й и 8-й элементы. После четверной сортировки элементы перегруппировываются - теперь каждый элемент группы отстоит от другого на 2 позиции - и вновь сортируются. Это называется двойной сортировкой. И наконец, на третьем проходе идет обычная или одинарная сортировка.

 

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

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

Приводимый ниже алгоритм не ориентирован на некую определенную последовательность расстояний и использует метод прямой вставки с условным переходом.

При использовании метода барьера каждая из сортировок нуждается в постановке своего собственного барьера, поэтому приходится расширять массив с [0..n ] до [-h1..n ].

Не доказано, какие расстояния дают наилучший результат, но они не должны быть множителями один другого. Д. Кнут предлагает такую последовательность шагов h (в обратном порядке): 1, 3, 7, 15, 31, …

То есть: h _m =2h _m-1+1 а количество шагов t = log₂n - 1.

При такой организации алгоритма его эффективность имеет порядок O (n^{1 .5})

Алгоритм сортировки Шелла

Обозначим

h[1..t] - массив размеров шагов

a[1..n] - сортируемый массив

k - шаг сортировки

x - значение вставляемого элемента

ShellSort

const t = 3

h(1) = 7

h(2) = 3

h(3) = 1

for m = 1 to t

k = h(m)

for i = 1 + k to n

x = a(i)

for j = i - k to 1 step -k

if x < a(j) then

a(j+k) = a(j)

else goto L endif

next j

L: a(j+k) = x

next i

next m

return