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

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

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

Разработаем функцию Binary_Search, определяющую индекс ячейки в упорядоченной части массива а, в которой должно размещаться некоторое число т.

Упорядоченная часть массива имеет границы индексов 1..last.

Обозначим l — индекс левого элемента исследуемого в холе поиска отрезка массива, r — правого, mid — величину, равную (1+r)/2. В начале поиска принимаем l =1, r=last.

Определяем величину mid и сравниваем значения: a[mid] и т.

Если a[mid] >m, то размещаемое число должно находиться в левой половине исследуемого диапазона, т. е. можно принять r=mid-1, в противном случае — в правой половине — 1=mid+1.

После этого процесс повторяется применительно к новому диапазону и заканчивается, когда r станет меньше 1. В этой ситуации искомый индекс равен значению 1.

При разработке функции на Паскале следует учесть, что в этом языке использование массивов с переменными границами не допускается. Поэтому придется использовать в числе параметров функции величину а типа arrtype:

 

function Binary_Search(last:word;var a:arrtype;m:word):word;

var l,r,mid:word;

begin

j:=1;

r:=last;

while 1<=r do

begin     

  mid:=(l+r) div 2;

  if a[mid]>m then r:=mid-1

              else l:=mid+1

end;

 Binari_Search:=l;

end;

 

Процедуры сортировки методом бинарных вставок, использующие приведенные функции, имеют вид:

 

procedure Binary_Insert_Sort(var a:arrtype);

var i:integer;

begin             

for i:=2 to n do

  if a[i]<a[i-l] then Insert(a,i,Binary_Search(i-l,a,a[i]))

  {Вставляем элемент a[i] на его место,

   найденное методом бинарного поиска

   на отрезке массива а с индексами от 1 до i-1}

end;

 

Разновидность метода вставок, использующая бинарный поиск места размещения очередного элемента, называется сортировкой бинарными вставками.

Сравним ее с вариантами, описанными выше (эти варианты сортировки носят название "метод простых вставок").

Когда при сортировке простыми вставками на соответствующем месте размещается 1-й элемент, то его значение сравнивается в среднем примерно с i/2 ранее отсортированными значениями; поэтому общее, число сравнений при этом равно (1+2+...+n) /2=n²/4, а это очень много, даже если n умеренно велико».

При использовании же бинарного поиска места размещения очередного элемента число сравнений значительно меньше. Например, если очередной элемент — 64-й, то его значение сначала сравнивается с 32-м; затем с 16-м или 48-м и т. д., так что искомое место будет найдено максимум после всего лишь шести сравнений. Общее же число сравнений для n элементов равно приблизительно nlog₂n, что существенно лучше, чем n² /4;

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

А поскольку в компьютере операция присваивания выполняется за значительно большее время, чем операция сравнения, то общая экономия времени будет незначительной, так что общее время работы при бинарном поиске, по существу, остается пропорциональным п²/2.

Это подтверждают и расчеты (табл. 4). Хотя для вещественных чисел сравнение выполняется медленнее, чем присваивание.

 

 

Таблица 4. Сравнительная характеристика методов
простых вставок и бинарных вставок

 

Метод	Количество элементов в массиве
	n=1000	n=2000	n=4000
Простые вставки	1,2	4,5	19,0
Бинарные вставки	1,0	3,5	14,2

 

 

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

Как показали расчеты, проверка условия a[i]<a[i-l] не приводит к увеличению продолжительности сортировки. В то же время если такую проверку не проводить, то в случаях, когда исходный массив упорядочен или близок к таковому, бинарный поиск потребует большего времени, чем методы поиска, описанные в начальных пунктах данного параграфа!

Этот пример показывает, что в ряде случаев "очевидное улучшение" программ оказывается намного менее существенным, чем кажется вначале, а иногда может на самом деле оказаться ухудшением.