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

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

Qulaylik va ravshanlik uchun bitta guruh elementlari bir xil rangda ko‘rsatilgan.

Misol:
1-qadam. r1=8, ya’ni (a[0], a[8]), (a[1], a[9]), ... , (a[7], a[15]).

12

8