Şell metodu ilə çeşidləmə
Göründüyü kimi yerinə salmaqla çeşidləmə alqoritminin işləmə sürəti N2-na mütənasibdir. Sürəti artırmaq üçün elə mexanizm olmalıdır ki, yazılar böyük sıçrayışla yerdəyişmələr edə bilsinlər. Bu cür metodlardan birini Şell təklif etmişdir. Bu metoda həmçinin azalan addımla çeşidləmə də deyilir.
Metodun izahı. Fərz edək ki, 16 açar çeşidlənir. Onları hər qrupda 2 açar olmaqla 8 qrupa bölək
(k1,k9),(k2,k10),....,(k8,k16).
Hər qrup ayrılıqda çeşidlənir. Sonra açarlar hər qrupda 4 açar olmaqla 4 qrupa bölünür.
(k1,k5,k9,k13),...,(k4,k8,k12,k16)
və bu qruplar da ayrılıqda çeşidlənir. 3-cü baxışda açarlar hər qrupda 8 açar olmaqla 2 qrupa bölünür.
(k1,k3,k5,k7,k9,k11,k13,k15),(k2,k4,k6,k8,k10,k12,k14,k16)
və bu qruplar ayrılıqda çeşidlənir. Və nəhayət 4-cü baxışda açarların hamısı bütövlükdə götürülüb çeşidlənir.
Hər baxışda həm qısa, həm də qismətən nizamlanmış siyahılar çeşidləndiyindən çeşidləməni sadə arayasalma üsulu ilə aparmaq məsləhətdir. Ümumi şəkildə addımların (bizim misalda 8,4,2,1) təyini belə aparıla bilər.
ht=n/2 ht-1=ht/2 ,......, h1=1
t=1 olduqda bu adi yerinə salma üsuluna çevrilir. Şell metodu ilə çeşidləmədə müqayisə əməliyyatlarını sayı şell metodu ilə çeşidləmədə müqayisə əməliyyatlarının sayı
MS=0.5n3/2
Şell metodunun alqoritmi (Şell alqoritmi)
R1,....,Rn yazıları açarların k1<=k2<=.....<=kn ardıcıllığı ilə çeşidləndikdən sonra həmin sahədə yerləşdirilir.
Çeşidləmə prosesində aralıq baxışlar ht,ht-1,h1 (h1=1) addımları ilə aparılır.
Xarici dövrə hazırlıq S=t, t-1,.....,1 üçün 2-ci mərhələni icra etməli və 7ci mərhələyə keçməli.
j-ya görə dövr. h:=hb qəbul edib ht<=kt+h alınır. 3-6 mərhələləri JERSAL alqoritmində 2-5 mərhələlərinə uyğundur.
Daxili dövrə hazırlıq. T:=j-h k:=kj R:=Rj qəbul etməli.
k və ki-nin müqayisəsi. Əgər k>=ki 6-cı mərhələyə keçməli.
Ri-ni sürüşdürüb i-ni azaltmalı. Ri+h:=Ri i:=i-h Əgər i>0 onda 4-cü mərhələyə qayıtmalı.
Yazının yerinə yazılması. Ri+h:=R 2-ci mərhələyə qayıtmalı.
Son. Alqoritmi qurmalı.
Dostları ilə paylaş: |