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

ÇEŞİDLƏMƏLƏR ANLAYIŞI. DAXİLİ VƏ XARİCİ ÇEŞİDLƏMƏ
Ç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.