6-mavzu. Ma'lumotlarni saralash algoritmlari. Saralashning yaxshilangan usullari va ularning samaradorligi

k-qadam. k-1 qadamda hosil bo‘lgan ketma-ketlik oddiy qo‘shish usuli orqali saralanadi.
Eslatma: r1>r2>…>rk-1>rk=1.

D.Shell taklif etgan oralig’lar ketma-ketligi umumiy holda quyidagicha:

D.Shell taklif etgan oralig’lar ketma-ketligi umumiy holda quyidagicha:

d 1=n/2 , d i=d i-1/2 , d k=1 eng yomon holatda ;

Algoritm samaradorligi - O(n2);

Eng yaxshi xolatda - O(n log2n);

O’rtacha vaqt – tanlangan qadamlarga bog’liq;

Xotira xajmi- O(n), qo’shimcha O(1)

Misol. Shell usuli yordamida massivni saralash jarayonini ko‘rib chiqamiz.

12

8

14

6

4

9

1

8

13

5

11

3

18

3

10

9

Алгоритм:

• 
  Dastlab bir-biridan 8ta pozitsiya (masofa)da turgan elementlar gruppalanadi va qo’yish usuli orqali saralanadi. Bu sakkizlik saralash deyiladi;
  
• 
  Keyin bir-biridan 4ta pozitsiya (masofa)da turgan elementlar gruppalanadi va qo’yish usuli orqali saralanadi. Bu to’rtlik saralash deyiladi;
  
• 
  Keyin bir-biridan 2ta pozitsiya (masofa)da turgan elementlar gruppalanadi va qo’yish usuli orqali saralanadi. Bu ikkitalik saralash deyiladi;
  
• 
  oxirida bittalik yani oddiy saralash amalga oshiriladi