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

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