ЯВНОГО элемента ( барьера ). Его можно лег^о приме-в этом случае, установив барьер Оо = х. (Заметим, что этого нужно расширить диапазон индексов в описании а Окончательный алгоритм представлен в виде

Программы 2.1.

procedure straightinsertion;

таг index, xi item;

begin

for / := 2 to и do

begin X :== ф] := x; j := г-1; while X .key < a[j] .key do

begin a[j+l] a[j]: J j-li end ;

a[J+l] := л:

* end

Программа 2.1. Сортировка простыми включенийми.

Анализ сортировки простыми включениями. Число С,- сравнений ключей при t-M просеивании составляет самое большее i-l, самое меньшее 1 и, если предположить, что все перестановки п ключей равновероятны, в среднем равно i/2. Число Л1,- пересылок (присваиваний) равно С,+ 2 (учитывая барьер). Поэтому общее число сравнений и пересылок есть

Cn,in = -1 Л1 , = 2(п-1)

Сср. = т( + -2) М . = (п' + 9п-Щ (2.4)

Сшах = т( + )-1 М™ах = 4( + 3 -4)

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

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

тировки называется сортировкой бинарными включеныщ он показан в программе 2.2.

procedure binarymertion;

vat i,J,l,r,m: index; x: Item; begin

for i :~ 2 to и do

beginx := op]; / := 1; f : /-I, while I rUQ beginm := (/+r)div2;

if X .key < a[m] .key then r := m-l else / := /и-f I end ;

for у :=: j-1 downto / do o[/+l] := ф];

ГЛ : x;

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

Анализ сортировки бинарными включениями. Место включения найдено, если ai.key х.кеу < йг.кеу. Таким образом, интервал поиска в конце должен быть равен I; это означает, что интервал из i ключей делится пополам [log2i] раз. Итак,

Мы аппроксимируем эту сумму с помощью интеграла

logxdx==x (log х - с) = п (log и - с) 4- с, (2.5)

где с = loge = 1/1п2 = 1.44269.... Количество сравнений не зависит от исходного порядка элементов. Но из-за округления при делении интервала поиска пополам действительное число сравнений для i элементов может быть на 1 больше ожидаемого. Природа этого перекоса такова, что в результате места включения в нижней части находятся в среднем несколько быстрее, чем в верхней части. Это дает преимущество в тех случаях, когда элементы изначально далеки от правильного порядка. На самом же деле минимальное число сравнений требуется, если элементы вначале расположены в обратном порядке, а максимальное - если они уже упорядочены. Следовательно, это случай неестественного ведения алгоритма сортировки:

C = ft(logn -loge±0.5).

К сожалению, улучшение, которое мы получаем, использу метод бинарного поиска, касается только числа сравненйй|

числа необходимых пересылок. В действительности по-а льку пересылка элементов, т. е. ключей и сопутствующей Лормации, обычно требует значительно больше времени, сравнение двух ключей, то это улучшение ни в коей мере является решающим: важный показатель М по-прежнему тается порядка п^. И в самом деле, пересортировка уже Рассортированного массива занимает больше времени, чем и-сортировке простыми включениями с последовательным поиском! Этот пример показывает, что очевидное улучшение часто оказывается намного менее существенным, чем кажется вначале, и в некоторых случаях (которые действительно встречаются) может на самом деле оказаться ухудшением. В конечном счете сортировка включениями оказывается не очень подходящим методом для цифровых вычислительных машин: включение элемента с последующим сдвигом всего ряда элементов на одну позицию неэкономна. Лучших результатов можно ожидать от метода, при котором пересылки элементов выполняются только для отдельных элементов и на большие расстояния. Эта мысль приводит к сортировке выбором.

2.2.2. Сортировка простым выбором

Этот метод основан на следующем правиле:.

1. Выбирается элемент с наименьшим ключом.

2. Он меняется местами с первым элементом Ui.

Эти операции затем повторяются с оставшимися п - 1 элементами, затем СП - 2 элементами, пока не останется только один элемент - наибольший. Этот метод продемонстрирован на тех же восьми ключах в табл. 2.2.

Таблица 2.2. Пример сортировки простым выбором

г

Начальные tcmnu

Программу можно представить следующим образом: Ьгг:= 1 to п- 1 do

be Jin присвоить k инд,е}ссдаименьшего элемента изаИ-... a[ft] ;

помедять местами а< и