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



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

Shell taklif etgandagi aлгоритм:

Shell taklif etgandagi aлгоритм:


Usulning g'oyasi. Dastlab, bu masofa d yoki N/2 ga tengdir, bu yerda N elementlarning umumiy soni.
Faraz qilaylik: d=N/2 bo’lsin.
1- qadamda har bir guruh bir-biridan N/2 masofada joylashgan ikkita elementni o'z ichiga oladi; ular bir-biri bilan taqqoslanadi va kerak bo’lsa,tartiblanadi (qo’yish orqali saralash yordamida!) ,ya’ni ularning joylari almashtiriladi. Natijada ozgina bo’lsada nisbatan tartiblangan ketma-ketlik olamiz.
Keyingi bosqichlarda ham shu kabi tekshirish va almashish amalga oshiriladi, lekin d masofasi d/2 ga qisqaradi va shunga mos ravishda guruhlar soni kamayadi.
Asta-sekin elementlar orasidagi masofa kamayadi va d=1 da massivdan o'tish oxirgi marta sodir bo'ladi(bu holda qo’yish orqali saralash bajariladi)

Shell saralashi (qisqarib boruvchi qadamlar orqali saralash)


Algoritm umumiy g’oyasi
Faraz qilaylik, a[0],a[1],a[2],…, a[n] boshlang‘ich elementlar ketma-ketligi bo‘lsin.
1-qadam. Boshlang‘ich ketma-ketlikning har r1 o‘rinda joylashgan elementlari guruhlanib, har bir guruh alohida qo‘yish usuli orqali saralanadi: ({a[0], a[r1], a[2*r1],…,}, {a[1], a[1+r1], a[1+2*r1],…,} v.h.).
2-qadam. Hosil qilingan ketma-ketlikda har r2 o‘rinda joylashgan elementlar guruhlanib, har bir guruh alohida saralanadi.
....................................................................................................................
k-qadam. k-1 qadamda hosil bo‘lgan ketma-ketlik oddiy qo‘shish usuli orqali saralanadi.

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