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

3.1. Çeşidləmənin birbaşa üsulları

Elementlər fikrən artıq hazır olan a₁,...,a_i-1 ardıcıllığına və ilkin ardıcıllığa bölünürlər.

i = 2-dən başlayarq hər bir addımda i-ni bir vahid artıraraq, ilkin ardıcıllıqdan i–ci element çıxarılır və hazır ardıcıllığa qoyulur, bu zaman o, lazım olan yerə araya salınmış olur (şək.64).
Alqoritmin mahiyyəti belə olur:
for i = 2 to n
x = a(i) x-i daxil etmək üçün а(1)…а(i) arasında yer tapırıq
next i



Şək.64.Bir başa qoşulmalı üsulla çeşidləmə

Düz qoşulmalı üsulu ilə çeşidləmənin iki alqoritmi vardır. Birincisi-maneəsiz

Maneəsiz düz qoşulma üsulu ilə çeşidləmə alqoritmi

Bu alqoritmin mənfi cəhəti ondan ibarət olur ki, bu halda struktur proqramlaşdırmanın texnologiyası pozulmuş olur və bu halda şərtsiz keçidlərin tətbiqi arzu olunmaz olur. Əgərsə daxili dövrü while kimi təşkil etsək, o zaman “maneəni” quraşdırmaq lazım gələcək ki, onsuz açarlar mənfi qiymətlərə malik olduqda, əhəmiyyətlilik itmiş olacaq və kompüter “asılı” vəziyyətdə qalacaqdır.

Birbaşa qoşulmalı alqoritmin effektivliyi

i-cini ələkdən keçirtdikdə, Ci açarlarının müqayisələr sayının ən böyüyü (i-1)-ə, ən kiçiyi isə - 1-ə bərabər olur; əgər fərz etsək ki, N açarların bütün yerdəyişmələri bərabər ehtimallı olarsa, o zaman müqayisələrin orta qiyməti = i/2 olacaqdır. Bir yerdən başqa yerə keçmə Mi=Ci+3 (maneə daxil olmaqla) olacaqdır. Minimal qiymət-ləndirmələr artıq nizamlanmış ilkin ardıcıl elementlər halında rast gəlinir, ən pisi isə - onlar əvvəlcədən əks qaydada yerləşmiş olduqda olur. Müəyyən bir mənada qoşulma köməkliyi ilə çeşidləmə həqiqi təbii davranışı nümayiş etdirir. Aydındır ki, göstərdiyimiz alqoritm davamlı çeşidləmə prosesini təsvir edir: bərabər açarlara malik olan elementlərin düzülüşü bu halda dəyişilməz qalır.
Massiv əks tərəfli çeşidlənəndə ən pis halda müqayisələrin sayı С_max = n(n - 1)/2, yəni, - О (n²). Yerdəyişmələrin sayı M_max = C_max + 3(n-1), yəni, - О (n²). Əgər massiv artıq çeşidlənmişsə, o zaman müqayisələr və yerdəyişmələr sayı minimal olacaqdır: C_min  = n-1; M_min = =3(n-1).