Mühazirə 1 Giriş Əsas anlayışlar. "Məlumat"

Ünvanın hesablanması metodu

Açarı elə seçmək olar ki, onun qiymətinə görə yazının yaddaşdakı ünvanı hesablana bilsin. Bu halda yazılar sabit uzunluqlu, açar isə tam ədədlə verilməlidir. Yazılar yaddaşda açarların qiymətlərinə görə nizamla yerləşdirilir.

Ünvanın hesablanması 2 variantla aparıla bilər. 1-ci variant o vaxt tətbiq olunur ki, açarların sayı yazıların sayından çox olmasın və strukturda eyni qiymətli açara malik olan yazılar olmasın. Yazının nömrəsi ilə açarın qiyməti arasındakı asılılığı belə göstərmək olar.
i=k₁-((c)0-const)
i-yazının nömrəsi, k1 i-ci yazının açarıdır.
Yazının ünvanı belə təyin olunur.
A=(i-1)l+A₀
A₀ strukturun yaddaşda başlanğıc ünvanı (1-ci yazının ünvanı), l – yazıların uzunluğudur.
2-ci variant yazının nömrəsi ilə açar arasındakı asılılığın xətti olmasına əsaslanır.

k_n-k₁ = n-1 və ya

k_i-k₁ i-1

i = 1+ k_i-k₁ (n-1)

k_n k₁

Bu variantda bir neçə yazının açarlarının qiymətlərinin eyni olması mümkündür. Odur ki, açarın nömrəsi kimi yuvarlaq tam ədəd tapıldıqdan sonra qonşu yazılar müqayisə yolu ilə baxılır və verilmiş açara uyğun yazı və ya yazılar seçilir.

Axtarışda ünvan göstəricilərindən istifadə olunması, açarın ünvana çevrilməsi metodları və bu məqsədlə tətbiq edilən randomlaşdırma üsulları verilmişdir.
Mühazirə 13

Nizamlama alqoritmləri

Çeşidləmə - bu seçilmiş parametr üzrə müntəzəm şəkildə yaddaşda verilənlərin yerləşməsi deməkdir. Müntəzəmlik verilənlər massivinin əvvəllindən sonuna qədər parametr qiymətinin artması (azalması) kimi nəzərdən keçirilir.
Verilənlərin emalı zamanı verilənlərin informasiya sahəsini və verilənlərin maşında yerləşməsini bilmək çox vacibdir.
Daxili və xarici kimi çeşidləməni fərqləndirirlər:
-daxili çeşidləmə - əməli yaddaşdakı çeşidləmədir;
-xarici çeşidləmə - xarici yaddaşdakı çeşidləmədir.
Əgər çeşidlənən yazılar böyük yaddaş həcmini tutmuş olsalar, bu zaman onların yerdəyişilməsi böyük xərclərə səbəb ola bilər. Onları azaltmaqdan ötrü çeşidləməni açarlar ünvanlarının cədvəlində aparırlar, yəni, göstəriciləri yenidən quraşdırırlar, massivin özü isə yerdəyişmə etmir. Bu – ünvanlar cədvəlinin çeşidləmə üsuludur. (şək.63).



Şək.63.Ünvanlar cədvəlinin çeşidləmə üsulu

Çeşidləmə zamanı yeni açarlara rast gəlinə bilər. Bu halda yaxşı olardı ki, çeşidləmədən sonra eyni olan açarları ilkin faylda olan qaydada yerləşdirək. Bu - davamlı çeşidləmədir.

Biz yalnız əlavə yaddaşdan istifadə etməyən çeşidləməni nəzərdən keçirəcəyik. Bu cür çeşidləmə “həmin yerdə də” adlanır.
Çeşidləmə effektivliyini bir neçə kriterilər üzrə nəzərdən keçirtmək olar:
•çeşidləməyə sərf olunan vaxt;
•çeşidləmə üçün tələb olunan əməli yaddaşın həcmi; 
•proqramın yazılmasına proqramçının sərf etdyi vaxt.
Birinci kriterini ayıraq. Çeşidləməyə sərf olunan vaxta ekvivalent olaraq, çeşidləmənin yerinə yetirilməsi zamanı müqayisələrin sayını və yerdəyişmələrin sayını hesab etmək olar.
•Müqayisələr və yerdəyişmələr sayına qayda aşağıdakı hüdudda yerləşir:
О (n log n)-dən О (n²)-a qədər; 
О (n) – ideal və nail oluna bilinməyən hadisədir.
Aşağıdakı çeşidləmə üsullarını fərqləndirirlər:
•ciddi (düz) üsullar;
•yaxşılaşdırılmış üsullar.
Ciddi üsullar:
•düz qoşulma üsulu;
•düz seçim üsulu;
•düz mübadilə üsulu.
Ciddi üsulların effektivliyi təxminən eyni olur.