O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti

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).
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.