Навигация
Сортування прямим включенням
43832
знака
1
таблица
0
изображений
1.1 Сортування прямим включенням
В основі розглядуваного методу лежить пошук для чергового елемента масиву відповідного місця у відсортованій частині із наступним включенням його в знайдену позицію. Таким чином елементи масиву умовно діляться на дві групи - вже "готову" послідовність a 1 , a 2 , ..., a i та вихідну послідовність. На кожному етапі, починаючи з i=2 та збільшуючи i кожен раз на 1, із вихідної послідовності вибирається один елемент і вставляється в потрібне місце у вже впорядковану послідовність. Очевидно, що початкова ліва послідовність буде "готовою", оскільки одноелементний масив завжди впорядкований. Цей алгоритм можна записати у вигляді послідовності команд :
for i:=2 to N do
begin
x:=a[i];
включення x на потрібне місце серед a[1], ..., a[i]
end;
Процес просіювання (пошуку потрібного місця для включення елемента x ) може припинитися при виконанні однієї із двох умов :
1) знайдено елемент a jз ключем, меншим ніж ключ у x ;
2) досягнутий лівий кінець "готової" послідовності.
Таким чином програмна реалізація методу прямого включення матиме вигляд процедури :
Procedure Straight_Insertion;
Var
i, j : integer; x : basetype;
Begin
for i:=2 to N do
begin
x:=a[i]; a[0]:=x; j:=i;
while x<a[j-1] do
begin
a[j]:=a[j-1];
j:=j-1
end;
a[j]:=x
end
End;
Використання додаткового елемента в масиві - "бар’єра" a[0]=x забезпечує гарантоване припинення процесу просіювання. Це дозволяє зменшити кількість логічних умов в заголовку цикла while до однієї, а кількість логічних операцій від 2i-1 до i на кожному етапі. Звичайно, при цьому необхідно попередньо розширити на один елемент масив a та діапазон допустимих значень індекса. На жаль, таке покращення ефективності по кількості порівнянь не зменшує об’єму перестановок елементів.
Аналіз прямого включення. Кількість порівнянь ключів Ci при i-ому просіюванні найбільше дорівнює i, найменше - 1, а середньоймовірна кількість - i/2. Кількість же перестановок (переприсвоєнь ключів), включаючи бар’єр, Mi=Ci+2. Тому для оцінки ефективності алгоритму у випадках початково впорядкованого, зворотньо впорядкованого та довільного масиву можна скористатися наступними співвідношеннями:
;
;
;
;
;
.
Очевидно, що розглянутий алгоритм описує процес стійкого сортування.
1.2 Сортування бінарним включенням
Алгоритм прямого включення можна значно покращити, якщо врахувати, що "готова" послідовність є вже впорядкованою. Тому можна скористатися бінарним пошуком точки включення в "готову" послідовність. Програмна реалізація такого модифікованого методу включення матиме вигляд процедури:
Procedure Binary_Insertion;
Var
i, j, m, L, R : integer; x : basetype;
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;
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) операцій порівняння вимагатиме більше часу, ніж у випадку послідовного сортування з прямим включенням. Очевидно, що кращий результат дадуть алгоритми, де перестановка, нехай і на велику відстань, буде пов’язана лише з одним елементом, а не з переміщенням на одну позицію цілої групи.
Похожие работы
... Висновки по розділу 3 У даному розділі диплома була розроблена автоматизована інформаційна система розрахунку прибутку на гірничо-збагачувальному підприємстві. Дана система була розроблена для підвищення ефективності роботи підприємства. В основу алгоритмів обробки даних покладені методи математичної статистики й оптимізаційні моделі. Для проектування і реалізації автоматизованої інформаційної ...
... стимулювати учнів до нових зусиль у роботі, до самостійного переборення труднощів – це істотна ознака майстерності вчителя. Розділ 2. Технологія організації самостійної роботи учнів на уроках у початковій школі 2.1 Дидактичні умови організації самостійної роботи молодших школярів Визначаючи дидактико-методичні підходи до організації самостійної роботи учнів, ми враховували творчі надбання ...
... · пошуковий механізм, який користувачі використовують як інтерфейс для взаємодії з базою даних. Засоби пошуку типу агентів, павуків, кроулерів і роботів використовуються для збору інформації про документи, які знаходяться в мережі Інтернет. Це спеціальні програми, які займаються пошуком сторінок в мережі, збирають гіпертекстові посилання з цих сторінок і автоматично індексують інформацію, яку ...
... Чарка, стакан 4 320 2 80 400 Столові прибори (комплект) 4 320 2 80 400 Далі наведемо характеристику посуду, який будуть використовувати в комплексному закладі ресторанного господарства (табл. 2.8–2.11). Таблиця 2.8. Характеристика та призначення класичного вітчизняного порцелянового та фаянсового посуду Найменування Розміри, мм Місткість, см3, порцій Призначення ...
0 комментариев