Сортировка бинарными включениями

Если воспользоваться отсортированностью «готовой» последовательности, то процесс вставки нового элемента может быть ускорен. Это достигается за счет применения бинарного (дихотомического) поиска места вставки очередного элемента. Программа приведена в листинге 8.4.

Листинг 7.4. Сортировка бинарными включениями

Procedure SortBinInsert (var a: TData);

Var

i,j,left,right,m: integer;

tmp        : integer;

Begin

for i:=2 to N do begin

  tmp:=a[i]; left:=1; right:=i-1;

  while left<=right do begin

  m:=(left+right)div 2;//определение индекса среднего элемента

    if tmp<a[m] then

    right:=m-1        // сдвиг правой

Else

   left:=m+1     //или левой границы

  end;

  for j:=i-1 downto left do a[j+1]:=a[j]; // сдвиг элементов

  a[left]:=tmp;     // вставка элемента на нужное место

end;

End; // BinInsert

Число сравнений C~N*logN, так как поиск места вставки ищется каждый раз только в половине интервала. Но это улучшение касается только числа сравнений. Поскольку пересылка элементов – более трудоемкая операция, то это улучшение не является решающим: число перестановок по-прежнему ~N².

Для больших N сортировка вставками оказывается не очень подходящим методом: сдвиг ряда элементов для вставки одного – неэкономно. Казалось бы, гораздо эффективнее переставлять только некоторые элементы и на большие расстояния. Действительно, такой метод сортировки есть: это сортировка Шелла. Мы рассмотрим ее несколько позже.

Сортировка обменом

Сортировка простым обменом

Сортировка методом пузырька – это трогательное название запоминают все. Но далеко не все знают, что этот метод в полной мере воплощает принцип обменной сортировки: сравниваются и обмениваются местами два соседних элемента. При чем здесь пузырек? Если представить массив высоким и узким сосудом с жидкостью, а элементы массива – пузырьками, вес которых пропорционален величине ключа элемента, то каждый проход по массиву заставляет пузырек подняться кверху и занять место, соответствующее его весу. Алгоритм приведен в листинге 7.5.

Листинг 7.5. Сортировка методом пузырька

Procedure SortBubble (var a: TData);

Var

i,j: integer;

tmp : integer;

Begin

for i:=2 to N do begin

for j:=N downto i do

if a[j-1]>a[j] then begin              // сравнение элементов

tmp:=a[j]; a[j]:=a[j-1]; a[j-1]:=tmp // обмен местами

End

End;

End;   

 

Шейкер-сортировка

Оптимизация предыдущего алгоритма включает в себя следующее:

• массив можно считать уже упорядоченным, если на последнем проходе не было ни одной перестановки элементов
• сравнение пар элементов можно производить только до места последней перестановки: раз не было перестановок, значит – дальше элементы упорядочены
• при прохождении массива слева направо (снизу вверх) поднимается легкий пузырек. Почему бы не двигаться по массиву в обратном направлении – сверху вниз, опуская тяжелый пузырек?

Эти моменты учтены в шейкер-сортировке (от англ. shake – трясти), приведенной в листинге 7.6.

Листинг 7.6. Шейкер-сортировка

Procedure SortShaker (var a: TData);

Var

j,left,right: integer;

tmp       : integer;

Last   :integer; // место последней перестановки

Begin

left:=2; right:=N; last:=N;

Repeat

for j:=right downto left do //поднимаются легкие пузырьки

if a[j-1]>a[j] then begin

tmp:=a[j]; a[j]:=a[j-1]; a[j-1]:=tmp;

last:=j

end;

left:=last+1; // запомнили место последней перестановки

for j:=left to right do //опускаются тяжелые пузырьки

if a[j-1]>a[j] then begin

tmp:=a[j]; a[j]:=a[j-1]; a[j-1]:=tmp;

last:=j

end;

right:=last-1; // запомнили место последней перестановки

until left>right;

End; //Shaker

 

Число сравнений в алгоритме простого обмена равно C=1/2(N²-N), а минимальное и максимальное количества пересылок равны: M_min=0, M_max~(N²-N). Наименьшее число сравнений в шейкер-сортировке C_min=(N-1) – это соответствует единственному проходу по упорядоченному массиву.

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

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

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

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

1, 4, 13, 40, 121, … , где step_k-1=3*step_k+1,

1, 3, 7. 15, 31, …где step_k-1=2*step_k+1.

В листинге 7.7 шаги выбирались по формуле step_k= step_k-1*3/5, начиная с step₁=N div 2 и заканчивая шагом, равным единице.

Листинг 7.7. Сортировка Шелла

---

Дата добавления: 2021-01-21; просмотров: 90; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!