6-ma’ruza. Saralash turlari va algoitmlar samardorligi. Saralashning qat’iy va yaxshilangan usullari. Reja

Algoritm samaradorlig:
O(n log n) – eng samarali usul.
Shell saralashi (qisqarib boruvchi qadamlar orqali saralash). To’g’ri qo’shish usulini 1959 yilda D. Shell tomonidan mukammallashtirish taklif qilingan. Quyidagi chizmada ushbu usul tasvirlangan:

Boshida bir biridan 4 qadamda joylashgan elementlar o’zaro guruhlanib saralash amalga oshiriladi. Bunday jarayon to’rtlik saralash deb ataladi. Birinchi o’tishdan keyin elementlar qayta guruhlanib, endi har ikki qadamdagi elementlar taqqoslanadi. Bu esa ikkilik saralash deb nomlanadi. Va nihoyat, uchinchi o’tishda oddiy yoki yakkalik saralashi amalga oshiriladi.
Bir qarashda mazkur usul bilan saralash amalga oshirilganda saralash jarayoni kamayish o’rniga ortib boradigandek tuyulsada, elementlarni o’rin almashtirishlar nisbatan kam amalga oshiriladi.
Ko’rinib turibdiki, bu usul natijasida tartiblangan massiv hosil bo’lib, har bir o’tishdan keyin saralashlar kamayib boradi. Eng yomon holatda oxirgi ishni yakkalik saralash amalga oshiradi.
Baryer usulidan foydalanilganda har bir saralash o’zining baryeriga ega bo’lishi lozim hamda dastur uning joyini aniqlashi uchun uni iloji boricha osonlashtirish lozim. Shuning uchun massivni [-h1..N] gacha kengaytirish lozim bo’ladi.
h[1..t] – qadamlar o’lchami massivi
a[1..n] - saralanayotgan massiv
k – saralash qadami
x – qo’shilayotgan element qiymati
Subroutine ShellSort
const t = 3;
h(1) = 5;
h(2) = 3;
h(3) = 1;
var
h: array [1..t] of integer;
a: array [1..n] of integer;
k, x, m, t, i, j: integer;
begin
for m = 1 to t do
begin
k:= h(m);
for i = k + 1 to n do
begin
x:= a(i);
for j = i-k downto k do
begin
if x < a(j ) then
a(j+k):= a(j);
else
goto 1;
end ;
end;
end;
1: a(j+1) = x ;
end;
end .

Umuman olganda, qanday qadamlar tanlanganda eng yaxshi natija olinishi isbotlanmagan bo’lsada, lekin bu qadamlar biri ikkinchisini ko’paytuvchilari bo’lmasligi lozimligi aniqlangan.

D. Knut qadamlarni quyidagicha ketma-ketligini taklif qilgan (teskari tartibda): 1,3,7,15,31,…,ya’ni: h_m-1=2h_m+1, h_t=1, t = [log₂n] - 1. Agar qadamlar ushbu ko’rinishda aniqlansa, algoritm samaradorligi tartibi O(n^1.2).