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

Cəld çeşidlənmə. Müxtəlif çeşidlənmə üsul effektivliyinin qiymətləndirilməsi

Bu üsul mübadilə çeşidləmə üsullarına aiddir. Əsasında seçilmişə görə münasibətdə açarların bölünmə metodikası durur (şək.67).

Şək.67. Cəld çeşidləmə 

Şəkildən göründüyü kimi 6-dan sol tərəfdə 6-dan kiçik olan açarlar, sağ tərəfdə isə - 6-dan böyük olan açarlar yerləşmişlər.

Çeşidləmənin mövcud olan üsulları içərisində Quick Sort ən effektli hesab olunur.

Onun effektivlik dərəcəsi belə olur: О (n log₂ n)


Açarların çevrilməsi. Çevrilmə funksiyasının çevrilməsi

Yerləşdirmə (xeşləmə) üsulu verilənlər strukturunda elementin yerləşmə məkanı barəsində məsələnin cəld həll olunmasına istiqamətlənmişdir. Yerləşdirmə üsulunda verilənlər adi massiv kimi təşkil olumuşdur. Buna görə də, H – açarları massiv indekslərinə çevirən əks etdirmədir, buradan da adətən bu üsula verilən ad əmələ gəlmişdir – “açarların çevrilməsi”. Qeyd etmək lazımdır ki, dinamiki yerləşdirmənin hər hansı bir proseduruna müraciət etməyə ehtiyac yoxdur, çünki, bütün massiv – bu, əsas, statiki obyektlərdən biri hesab olunur. Açarların çevrilmə üsulu elə bir məsələlər üçün tez-tez istifadə olunur ki, orada uğurla ağaclardan da istifadə etmək mümkün olsun.

Əgər hər bir açar bir müraciət nəticəsində çüxarılmalı olarsa, o zaman bu cür cədvəlin daxilində yazının vəziyyəti yalnız bir açardan asılı ola bilər. O, digər açarların yerləşməsindən asılı olmamalıdır, halbuki ağacda bu cür asılılıq olmur. Bu cür cədvəlin təşkil olunmasının ən effektiv üsulunu massiv təşkil edir.
Fərz edək ki, hər hansı bir firma detallar istehsal edir və onu 7 rəqəmli ədədlə kodlaşdırır. Tam 7 rəqəmli açardan istifadə etməklə, düz indeksləşdirməni tətbiq etmək üçün 10 milyon elementlərdən ibarət olan massiv lazım ola bilərdi. Aydındır ki, bu böyük yaddaş fəzasının itməsinə gətirib çıxara bilərdi, çünki, tamamilə inanılmamaq dərəcədə demək olar ki, hər hansı bir firma mindən artıq məmulatlar adına malik olsun. Buna görə də, açarın məhdud diapazon daxilində hər hansı bir tam ədədə çevrilmə üsulu zəruridir.
Əgər massivdə məmulat barəsində yazı indeksi kimi məmulatın son 3 rəqəmlərindən istifadə olunsa, o zaman bütün faylın saxlanılması üçün 1000 elementlərdən ibarət olan massiv kifayət edər. Bu massiv 0-dan 999 daxil olmaqla tam ədədlə indeksləşdirilir.