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

End;

End;

Else

Begin

Var

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

End;

End;

Begin

Var

Type

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

Элементы массива условно разделяются на «готовую» последовательность a[1]…a[i] и «входную»: a[i+1]…a[N]. На каждом шаге, начиная с i=2, берут i-тый элемент массива – 1‑ый элемент «входной» последовательности и «вставляют» в нужное место «готовой» последовательности. Поскольку «вставить» между элементами массива новый элемент невозможно, приходится сдвигать j-тый элемент вправо, если вставляемый элемент меньше j-того, пока не найдется нужное место. Эта деятельность может закончиться при двух различных условиях:

q Найден элемент a[j], меньший, чем вставляемый элемент.

q Достигнут левый край массива.

Чтобы не использовать неэффективный цикл с двумя условиями, применим метод барьера, установив его в нулевой элемент массива. Для этого придется расширить диапазон индексов в описании массива до 0..N. Программа приведена в листинге 8.3.

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

TData = array[0..N] of integer;

procedure SortInsertion(var a: TData); // Внимание! Массив должен

// начинаться с нуля!

i,j : integer;

tmp : integer;

for i:=2 to N do begin

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

a[0]:=tmp; // установка барьера

while tmp<a[j] do begin

a[j+1]:=a[j]; // сдвинуть элемент

j:=j-1

a[j+1]:=tmp // поставить элемент на свое место

end; // SortInsertion

В сортировке простыми вставками число сравнений ключей при помещении i-того элемента на свое место составляет в среднем C_i ~i/2. Число пересылок M_i=C_i +2. Наименьшие числа появляются, если элементы с самого начала упорядочены, а наихудший случай встречается, если элементы расположены в обратном порядке.

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

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

procedure SortBinInsert (var a: TData);

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

tmp : integer;

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 // сдвиг правой

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

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

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

end; // BinInsert

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

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