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

Birbaşa qoşulma və seçim üsulları ilə çeşidləmələr

 

Verilənlərin emalı zamanı elementin həm informasiya sahəsini, həm də onun maşının yaddaşında yerləşməsini bilmək vacibdir. Bu məqsədlər üçün çeşidləmədən istifadə olunur. Beləliklə, çeşidləmə - bu, verilənlərin yaddaşda onların açarları üzrə müntəzəm şəklində yerləşməsi deməkdir. Müntəzəmlik açar qiymətinin massivdə başlanğıcdan sona qədər artması kimi nəzərdən keçirirlər.

Çeşidləmənin aşağıdakı tipləri olur:

-daxili çeşidləmə - bu, maşının əməli yaddaşında baş verən çeşidləmədir;

-xarici çeşidləmə- bu, xarici yaddaşda baş verən çeşidləmədir.

Əgər çeşidlənən yazılar yaddaşın böyük həcmini tutursa, onaların yerlərinin dəyişdirilməsi böyük xərclər tələb edir. Bunu azaltmaqdan ötrü çeşidləməni açarların ünvanları cədvəlində aparırlar, göstəricilərin yerlərini dəyişdirirlər, yəni, massivin özü yerini dəyişdirmir. Bu, ünvanlar cədvəlinin çüşidlənmə üsuludur.

Çeşidləmə zamanı eyni açarlara rast gəlmək mümkün ola bilər. Bu halda çeşidləmə zamanı yaxşı olardı ki, çeşidləmədən sonra eyni olan açarlar ilkin faylda olan kimi yerləşmiş olsunlar. Bu davamlı çeşidləmədir.

Ç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ı üçün proqramçının sərf etdiyi vaxt.

Birinci kriteni ayıraq, çünki, biz yalnız “elə həmin yerdə” çeşidləmə üsulunu nəzərdən keçirəcəyik, yəni, çeşidləmə prosesi üçün əlavə yaddaş ehtiyatda saxlamayacayıq. Sərf olunmuş vaxta ekvivalent olaraq, çeşidləmə zamanı yerinə yetirilən müqayisələrin və yerdəyiş-mələrin sayını hesab etmək olar.

 Çeşidləmələrin aşağıdakı üsulları mövcuddurlar:

-ciddi (düz) üsullar;

-mürəkkəbləşdirilmiş üsullar

Düz üsuların üstünlüklərini nəzərdən keçirək:

1.Bu üsulların proqramlarını yüngül başadüşmək olur və onlar qısa olurlar. Yadda saxlamaq lazımdır ki, proqramların özləri də yaddaşda yer tuturlar.

2. Düz üsullar əksər çeşidləmələrin əsas prinsiplərinin xarakterik xassələrinin izahı üçün xüsusilə rahat olur.

3. Mürəkkəbləşdirilmiş üsullar çox da böyük olmayan əməliyyatları tələb edirlərlər, amma bu əməliyyatlar adətən, özləri daha mürəkkəb olurlar və buna görə də, kifayət qədər kiçik sayda elementlər üçün düz üsullar daha sürətli olurlar, amma, elementlərin sayı çox olduqda, onlardan istifadə etmək olmaz.

“Elə həmin yerdə” çeşidləmə üsullarını onların prinsiplərinin təyin edilməsinə uyğun olaraq, 3 kateqoriyaya bölmək olar:

1. Araya salma köməkliyi ilə çeşidləmə (by insertion)

2. Seçim köməkliyi ilə çeşidləmə (by selection)

3. Mübadilə köməkliyi ilə çeşidləmə (by exchange)

 Araya salma üsulu ilə çeşidləmə

Bu cür üsul kart oyunlarında geniş istifadə olunur. Elementlər (kartlar) xəyalən artıq “hazır” olan ardıcıllığa a(1),...,a(i-1) və ilkin ardıcıllığa bölünürlər. i=2-dən başlayaraq, hər bir addımda i-nin qiymətini bir vahid artıraraq, ilkin ardıcıllıqdan i-ci element çıxarılır və hazır olan ardıcıllğa qoyulur, bu halda o lazımi yerə salınmış olur.

Düz araya salma çeşidləmə alqoritmi belə olacaqdır:

for x=2 to n do

   x=a[i]

     x-in a[1]...a[i] arasında uyğun yerə salınması

end
Uyğun yerin axtarışının real prosesində rahat olardı ki, müqayisələri növbələməklə, cari elementi növbəti a(j) elementi ilə müqayisə edək, sonra isə

 - ya x boş olan yerə salınsın,

 - ya da ki, a(j) sağa sürüşdürülsün (ötürülsün) və proses sola “getmiş olsun.

Bir amilə diqqət vermək lazımdır ki, ələmək prosesi aşağıdakı iki şərtlərdən birinin yerinə yetirilməsi ilə bitə bilər:

1. Tapılmış a(j) elementinin açarı x elementinin açarından kiçikdir.

2. Hazır ardıcıllığın sol sonuna çatılmışdır.

 Düz seçim üsulu ilə çeşidləmə

Ümumi halda çeşidləmə - bu, obyektlərin verilmiş çoxluğunun hər hansı müəyyən bir qaydada yenidən qruplaşma prosesidir. Çeşidləmənin məqsədi bu cür çeşidlənmiş çoxluqda növbəti elementin axtarışını yüngülləşdirməkdir. Bu demək olar ki, universal, fundamental fəaliyyətdir. Biz çeşidlənmiş obyektlərə telefon kitablarında, gəlir vergisi siyahılarında, kitablar mündəricatında, kitabxanalarda, lüğətlərdə, saxlanılan obyektlərin axtarışı lazım olan hər yerdə olan anbarlarda rast gəlirik.

Beləliklə, əgər söhbət verilənlərin emalından gedirşəo zaman çe- şidləmə barəsində danışıqlar yerinə düşür və vacibdir. Bildiyimiz kimi, verilənlərin çeşidlənməsi digəriləri ilə müqayisədə daha yüngül alınır. Bununla bərabər, bizim ilk əvvəlki çeşidləməyə olan marağımız ona əsaslanırdı ki, alqoritmləri quran zaman biz bir çox son dərəcə fundamental yollara rast gəlirik. Bu məsələnin müzakirəsi zamanı bizim rast gəldiyimiz bir sıra üsullar olmuşdu. Xüsusi halda, çeşidləmə - bu, həddindən artıq cürbəcür olan alqoritmlərin nümayiş edilməsi üçün ideal obyektdir, onlar hamısı eyni bir məsələ üçün ixtira olunmuş , bir çoxları müəyyən mənada optimal olurlar, çoxusu isə özlərinin üstünlüyünə malik olurlar. Buna görə də, bu həm də ideal obyekt olub, alqoritmlərin məhsuldarlığının təhlilinin zəruriliyini nümayış etdirir. Eyni zamanda da, çeşidləmə misalları vasitəsilə göstərmək olar ki, alqoritmləri mürəkkəbləşdirmə yolu ilə effektivlikdə əhəmiyyətli dərəcədə uğur qazanmaq olar.

        Yeni elementin araya salındığı hazır olan ardıcıllğın artıq nizamlanmış olduğunu nəzərə alaraq, düz araya salma alqoritmini bir qədər yaxşılaşdırmaq olar. Onda araya salma yerini ikilik (binar) axtarış üsulu ilə axtarılmalıdır. Bu cür yaxşılaşdırılmış alqoritm ikilik araya salma üsulu adlanır (yarıya bölməklə, düz araya salma üsulu). Lakin, çeşidlənmə elementlərinin sayı kifayət qədər böyük olan halda bu alqoritmin tətbiq olunması özünü doğruldur.  

 
Mühazirə 15