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

Şell çeşidlənməsi

Çeşidləmənin yaxşılaşdırılmış üsuluna aşağıdakıları aid etmək olar:

-Şell çeşidləməsi (azalan addımla çeşidləmə)
-Cəld çeşidləmə (Quick Sort)
1959-cu ildə D.Şell tərəfindən düz qoşulma üsulunun köməkliyi ilə təkmilləşdirilmiş çeşidləmə təklif edilmişdi. Başlanğıc addımı 4-ə bərabər olan onun çeşidlənməsi şək.66-da verilmişdir.



Şək.66.Şell çeşidləməsi

Əvvəlcə bir-birindən 4 məsafəsində duran elementlər ayrıca qruplaşdırılır və qruplarda çeşidlənirlər. Bu cür proses dördlük çeşidləmə adlanır. Bizim misalda 8 elementlər vardır və hər bir qrup iki elementlərdən ibarət olur, yəni, 1-ci və 5-ci elementlər, 2-ci və 6-cı, 3-cü və 7-ci və, nəhayət, 4-cü və 8-ci elementlər. Dördlük çeşidləmədən sonra elementlər yenidən qruplaş-dırılırlar – indi qrupun hər bir elementi digərindən 2 mövqe geridə qalır – və yenidən çeşidlənirlər. Bu ikilik çeşidləmə adlanır. Ən nəhayət, üçüncü keçiddə adi və ya bir qat çeşidləmə aparılır.

İlk baxışdan şübhəli qala bilərik: əgər çeşidləmənin bir neçə prosesləri lazımdırsa və bunların hər birinə bütün elementlər qoşulurlarsa, onda onlar qənaət etmək əvəzinə, daha çox iş əlavə etməyəcəklərmi? Lakin, hər bir mərhələdə ya nisbətən az elemenlər çeşidlənirlər, ya da ki, elementlər artıq kifayət qədər yaxşı nizamlanmışlar və nisbətən bir qədər yenidən yerdəyişmə tələb edirlər.
Aydndır ki, bu cür üsul nəticədə nizamlanmış massiv verəcəkdir və əlbəttə ki, o dəqiqə görünür ki, hər bir keçid əvvəlkilərlə müqayisədə yalnız udur; həmçinin, o da aydındır ki, sonuncunun vahid olması şərtilə, qruplarda olan məsafəni müxtəlif cür azaltmaq olar, doğrudan da, ən pis halda sonuncu keçid demək olar ki, bütün işi görür.
Aşağıda verilmiş alqoritm məsafələrin hər hansı bir müəyyən ardıcıllığına yönəlməmiş və şərti keçidli düz araya salma üsulundan istifadə edir.
Maneə üsulundan istifadə etdikdə, çeşidləmələrdən hər birisi özünün özəl maneəsinin qurulması üçün ehtiyacı olur, buna görə də, massivi [0..n]-dan [-h1..n]-ə qədər genişləndirməyə məcbur oluruq.
Hansı məsafələrin ən yaxşı nəticə verməsi sübut olunmamışdır, amma onlar bir-birinə vurulanlar kimi olmamalıdırlar. D.Knuth addımlarının aşağıdakı ardıcıllığını (əks qaydada) təklif etmişdir: 1, 3, 7, 15, 31, …
Yəni:  h _m  =2h_m-1+1, addımların sayı isə t = log₂n - 1.
Alqoritm bu cür təşkil olunduqda, onun effektivlik dərəcəsi belə olacaqdır: O ( n^1.5)