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

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