Курсовая работа: Порівняльний аналіз ефективності та складності швидких алгоритмів сортування масивів
for j:=i downto R+1 do
a[j]:=a[j-1];
a[R]:=x
end
End ;
Аналіз бінарного включення. Зрозуміло, що кількість порівнянь у такому алгоритмі фактично не залежить від початкового порядку елементів. Місце включення знайдено, якщо L=R . Отже вкінці пошуку інтервал повинен бути одиничної довжини. Таким чином ділення його пополам на i -ому етапі здійснюється log(i) раз. Тому кількість операцій порівняння буде:
, де 
, 
.
Апроксимуючи цю суму інтегралом, отримаємо наступну оцінку :
, де 
.
Однак істинна кількість порівнянь на кожному етапі може бути більшою ніж log(i) на 1 . Тому
.
Нажаль покращення, що породженні введенням бінарного пошуку, стосується лише кількості операцій порівняння, а не кількості потрібних переміщень елементів. Фактично кількість перестановок M залишається величиною порядку N2 . Для досить швидких сучасних ЕОМ рух елемента, тобто самого ключа і зв’язаної з ним інформації, займає значно більше часу, ніж порівняння самих ключів. Крім того сортування розглядуваним методом вже впорядкованого масиву за рахунок log(i) операцій порівняння вимагатиме більше часу, ніж у випадку послідовного сортування з прямим включенням. Очевидно, що кращий результат дадуть алгоритми, де перестановка, нехай і на велику відстань, буде пов’язана лише з одним елементом, а не з переміщенням на одну позицію цілої групи.
1.3 Сортування прямим вибором
На відміну від включення, коли для чергового елемента відшукувалося відповідне місце в "готовій" послідовності, в основу цього методу покладено вибір відповідного елемента для певної позиції в масиві. Цей прийом базується на таких принципах :
1) на i -ому етапі серед елементів a i , a i+1 , ..., a N вибирається елемент з найменшим ключем a min ; 2) проводиться обмін місцями a min таa i .
Процес послідовного вибору і перестановки проводиться поки не залишиться один єдиний елемент - з самим найбільшим ключем.
Такий алгоритм можна записати у вигляді послідовності команд :
for i:=1 to N-1 do
begin
k:=номер найменшого ключа серед a[i], ..., a[N];
обмін місцями a[k] та a[i]
end;
А програмна реалізація методу прямого вибору матиме вигляд процедури
Procedure Straight_Selection;
Var
i, j, k : integer; x : basetype;
Begin
for i:=1 to N-1 do
begin