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

14	6	4	9	1	8	13	5	11	3	18	3	10
9

12

8

14

6

4

9

1

8

13

5

11

3

18

3

10

9

2-qadam. r2=4, ya’ni (a[0], a[4], a[8], a[12]), ..., (a[3], a[7], a[11], a[15]).

12

5

11

3

4

3

1

8

13

8

14

6

18

9

10

9

3-qadam. r3=2, ya’ni (a[0], a[2], a[4], a[6], a[8], a[10], a[12], a[14]), (a[1], a[3], a[5], a[7], a[9], a[11], a[13], a[15]).

4

3

1

3

12

5

10

6

13

8

11

8

18

9

14

9

4-qadam. r4=1, ya’ni (a[0], a[2], … , a[15]).

1

3

4

3

10

5

11

6

12

8

13

8

14

9

18

9

1

3

3

4

5

6

8

8

9

9

10

11

12

13

14

18

Shell saralash usulining yagona tavsifi- har bir o‘tishdan keyin qadamlarni to‘g‘ri tanlash kerak.

• Garchi taqqoslashlar soni bir muncha ortib borsada, elementlarni o‘rinlashtirishlar ancha kam bo‘ladi.
• Bu usul natijasida har bir o‘tishdan keyin saralashlar kamayib boradi. Eng yomon holatda oxirgi ishni yakkalik saralash amalga oshiradi.

Qanday qadamlarda yaxshi natija olish mumkinkigi isbot qilinmagan, ammo qadamlar biri ikkinchisiga ko’paytuvchi bo’lishi mumkin emas.

Qanday qadamlarda yaxshi natija olish mumkinkigi isbot qilinmagan, ammo qadamlar biri ikkinchisiga ko’paytuvchi bo’lishi mumkin emas.

D.Knut (Д. Кнут) qadamlar uchun quyidagicha ketma-ketlikni taklif etgan (teskari tartibda): : 1, 3, 7, 15, 31, …

yani: h m-1 = h m + 1, t = log2n - 1.

Bunday algoritm uchun samaradorlik ko’rsatkichi O ( n1.2) ga teng..

R.Sedjvik taklif etgan qadamlar:
Usul samaradorligi:
O‘rtacha holat - O(n7/6),
Eng yomon holat - O(n4/3).
Eslatma
Sedjvik usuli orqali qadamlar tanlanayotganda, agar 3*inc[s]>n bo‘lsa, u holda eng katta qadam inc[s-1] bo‘ladi.

Piramidasimon saralash haqida qisqacha ma’lumot:

1)Bu pufaksimon usulning takomillashtirilgan holidir.

2) Binar saralash daraxtini(?) ,ya’ni massiv elementlarini binar daraxt kabi tashkil etishni ko’zda tutadi.

D. Uilyams tomonidan ixtiro qilingan piramidasimon saralash usuli an'anaviy usullarni daraxtlar yordamida saralash orqali takomillashtirililgan usuli hisoblanadi. Piramidasimon saralash (yoki uymli saralash, HeapSort) — bu ikkilik uyum ma'lumotlar tuzilmasiga asoslangan saralash usulidir. Bu usul tanlash orqali saralash usuliga o'xshaydi. Bu yerda biz birinchi navbatda eng maksimal elementni qidiramiz va uni oxiriga qo'yamiz. Keyinchalik, qolgan elementlar uchun xuddi shu operatsiyani takrorlaymiz.
Piramidasimon saralash (yoki uymli saralash, HeapSort)
Piramidali saralash algoritmining asosida binar daraxtning piramida dеb ataluvchi maxsus turidan foydalanish yotadi. Bunday binar daraxt tugunlarining qiymati eng yaqin avlodlari qiymatidan doimo katta bo’ladi.Saralash jarayoni piramida qurilishidan boshlanadi. Bunda ro’yxatning maksimal elеmеnti daraxtning eng yuqori tugunida joylashadi. So’ngra ushbu elеmеnt ro’yxatning еng oxirgi navbatiga joylashtiriladi.Elеmеnti olingan piramida esa qaytadan quriladi.Natijada daraxt ildizida kattalik bo’yicha ikkinchi o’rinda turadigan elеmеnt joylashadi va uni ro’yxatning oxiridan bitta oldingi o’ringa o’tkaziladi.Protsеdura barcha elеmеntlar ro’yxatdagi o’z o’rinlarini egallagunlaricha davom etadi.