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

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

const n=20; type item= integer; index=0..n; var a:array [1..n] of item; I,j:index; x:item; begin for i:=2 to n do begin x:=a[i]; l:=1;

r:=i-1; while l<=r do begin m:=(l+r) div 2; if x<a[m] then r:=m-1 else l:=m+1; end; for j:=i-1 downto l do begin a[j+1]:=a[j]; a[l]:=x;

end; end; end;

Анализ сортировки бинарного включения

Кол-во сравнений не зависит от исходного порядка эл-тов, но из-за округления при делении пополам действительная число сравнений для I-го эл-та может быть на 1 больше ожидаемого. В результате места включ. в нижней части находятся быстрее чем в верхней. Это дает преимущество в случаях когда эл-ты изначально далеки от правильного порядка. Мин. число сравнений если в начале расположены в обратном порядке и макс. – если они упорядочены => этот случай ниестественного поведения алгоритма сортировки.

Улучшение которое мы получаем применяя бинарный поиск касается только числа сравнений. Число пересылок это более важный показатель, т. к. пересылки требуют большего времени, здесь m остается порядка m², поэтому улучшение не является решающим, а если массив уже почти рассортирован алгоритм занимает больше времени чем СПВ с посл. включением.

Не нашли, что искали? Воспользуйтесь поиском: