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

Şell metodu ilə çeşidləmə

Göründüyü kimi yerinə salmaqla çeşidləmə alqoritminin işləmə sürəti N²-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
(k₁,k₉),(k₂,k₁₀),....,(k₈,k₁₆).
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.
(k₁,k₅,k₉,k₁₃),...,(k₄,k₈,k₁₂,k₁₆)
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.
(k₁,k₃,k₅,k₇,k₉,k₁₁,k₁₃,k₁₅),(k₂,k₄,k₆,k₈,k₁₀,k₁₂,k₁₄,k₁₆)
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.
h_t=n/2 h_t-1=ht/2 ,......, h₁=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.5n^3/2


Şell metodunun alqoritmi (Şell alqoritmi)

R₁,....,R_n yazıları açarların k₁<=k₂<=.....<=k_n ardıcıllığı ilə çeşidləndikdən sonra həmin sahədə yerləşdirilir.

Çeşidləmə prosesində aralıq baxışlar h_t,h_t-1,h₁ (h₁=1) addımları ilə aparılır.

1. 
   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.
   
2. 
   j-ya görə dövr. h:=h_b qəbul edib ht<=k_t+h alınır. 3-6 mərhələləri JERSAL alqoritmində 2-5 mərhələlərinə uyğundur.
   
3. 
   Daxili dövrə hazırlıq. T:=j-h k:=k_j R:=R_j qəbul etməli.
   
4. 
   k və k_i-nin müqayisəsi. Əgər k>=k_i 6-cı mərhələyə keçməli.
   
5. 
   R_i-ni sürüşdürüb i-ni azaltmalı. R_i+h:=R_i i:=i-h Əgər i>0 onda 4-cü mərhələyə qayıtmalı.
   
6. 
   Yazının yerinə yazılması. R_i+h:=R 2-ci mərhələyə qayıtmalı.
   
7. 
   Son. Alqoritmi qurmalı.