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

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

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

• Dastlab bir-biridan 4ta pozitsiya (masofa)da turgan elementlar gruppalanadi va qo’yish usuli orqali saralanadi. Bu to’rtalik 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

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.