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