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



Yüklə 15,83 Kb.
səhifə2/4
tarix22.10.2023
ölçüsü15,83 Kb.
#159726
1   2   3   4
Ma\'lumotlarni saralash algoritmlari. Saralashning yaxshilangan u-azkurs.org

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.
....................................................................................................................

Yüklə 15,83 Kb.

Dostları ilə paylaş:
1   2   3   4




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