Ma’lumotlar tuzilmasi va algoritmlar

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.

6-ma’ruza.
Chiziqli ma’lumotlar tuzilmalari. Statik va dinamik massivlar. Chiziqli konteynerlar va ularni qo‘llash.


Reja.

1. 
   Chiziqli ma’lumotlar tuzilmalari .Statik ma’lumotlar tuzilmasi haqida tushuncha.
   
2. 
   Stek tuzilmasi va uni dasturda amalga oshirish, ustida amal bajarish
   
3. 
   Navbat tuzilmasi va dasturda ifodalanishi, ustida amal bajarilishi
   
4. 
   Deklar. Ustida amal bajarish
   

Kalit so’zlar: Chiziqli ma’lumotlar tuzilmalari, navbat, stek, dek, yarimstatik tuzilmalar.
Kalit so’zlar: statik ma’lumotlar tuzilmasi, tuzilma uzunligi, xotira, massivlar, matrisalar, strukturalar, funksiyalar


Chiziqli MT – bu elementlari qat’iy tartiblangan yani 1- va oxirgi elementidan tashqari xar bir elementi uchun aniq o’zidan oldingi va keyingi element mavjud bo’lgan tuzilmadir. Elementlari xotirada ketma ket yacheykalarda joylashadi. Misol: massiv, satr,vector, navbat, stek,dek kabilar


Chiziqsiz MT – bu elementlari qat’iy tartiblanganmagan tuzilmadir:daraxt,graf