7-8-ma’ruza. Saralashning sodda algoritmlari. Saralashning yaxshilangan algoritmlari (4 soat) Reja

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
2
n] - 1. Agar qadamlar 
ushbu ko’rinishda aniqlansa, algoritm samaradorligi tartibi O(n
1.2
). 
 
Nazorat savollari 
1. Saralash deganda nimani tushunasiz? 
2. Saralashning asosiy usullarini aytib bering. 
3. Saralashning qaysi usulari qat’iy usulga tegishli? 
4. Saralashning yaxshilangan usullarini aytib bering. 
5. Qanday saralash turg’un deyiladi? 
6. To’g’ridan-to’g’ri qo’shish usuli g’oyasi nimadan iborat? 
7. To’g’ridan-to’g’ri tanlash usuli g’oyasi nimadan iborat? 
8. To’g’ridan-to’g’ri almashtirish usuli g’oyasi nimadan iborat? 
9. Yuqoridagi usullarning bir biridan farqini aytib bering. 
10. Qaysi saralash usuli eng samarali bo’lib hisoblanadi? 
11. Shell usuli qaysi asosiy saralash usuliga tegishli? 
Adabiyotlar. 
1. Adam Drozdek. Data structure and algorithms in C++. Fourth edition. 
2013. Chapter 9. 

---