Сортировка с помощью двоичного включения

Алгоритм сортировки с прямыми включениями легко можно улучшить, пользуясь тем, что готовая последовательность a[1], a[2], .., a[i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее. Очевидно, что здесь можно применить бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения. То есть при поиске места вставки очередного элемента просматриваем не все элементы, а только "средние".

Рассмотрим пример сортировки по возрастанию восьми случайно выбранных чисел 44 55 12 42 18 19 06 67. При i=6 отсортированная последовательность состоит из пяти чисел 12 18 42 44 55. Очередной элемент 19 необходимо вставить в последовательность. Поиск места будет проходить следующим образом: находим средний элемент отсортированной последовательности. Это 42. Если он больше вставляемого элемента, то находим средний элемент для левой части последовательности относительно элемента 42, иначе находим средний элемент правой части последовательности относительно 42. Следующий средний - 18. Повторяем сравнения и т.д.

Такой модифицированный алгоритм сортировки называется методом с двоичным включением.

Он реализуется следующей процедурой:

{ Двоичного включения }

procedure bin_insert(var a:mass; n:integer);

var i,j,m,R,L,x:integer;

begin

for i:=2 to n do

begin x:=a[i]; L:=1; R:=i;

While L<R do

begin

m:=(L+R) div 2; { Находим индекс среднего элемента }

if a[m]<=x then L:=m+1 else R:=m;

end;

{ Дальше сдвигаем массив с позиции R+1 до i a[R+1],…,a[i] на одну позицию вправо, начиная с места i }

for j:=i downto (R+1) do a[j]:=a[j-1];

a[R]:=x;

end; { Цикла по i }

end; { bin_insert }

Место включения элемента x в последовательность обнаружено когда l=r. Здесь улучшения, порожденные введением двоичного поиска, касаются лишь числа сравнений, а не числа необходимых продвижек (перестановок) чисел.

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