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


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



Yüklə 2,77 Mb.
səhifə3/5
tarix19.10.2023
ölçüsü2,77 Mb.
#157156
1   2   3   4   5
Ki7ZXv2TBWdP77kRVfHw6yOj59bROa6ispt4FVYV

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


Yüklə 2,77 Mb.

Dostları ilə paylaş:
1   2   3   4   5




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin