“Маълумотлар тузилмаси ва алгоритмлар” фанига кириш

• Reja:
• 1. Shell saralashi;
• 2. Piramidasimon saralash;
• 3. Tez saralash (Quicksort).

• 3-Mavzu: Saralashning yaxshilangan usullari

Shell saralashi (qisqarib boruvchi qadamlar orqali saralash)

• Algoritm g’oyasi

• Izoh

• Shell saralash 1959 yilda D.SHell tomonidan taklif qilingan bo‘lib, qo‘shish orqali saralashning modifikatsiyasi hisoblanadi.

• 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‘shish 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.

• Eslatma: r1>r2>…>rk-1>rk=1.

• Misol:

• 1-qadam. r1=8, ya’ni (a[0], a[8]), (a[1], a[9]), ... , (a[7], a[15]).

12

8

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

11

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

• Izoh

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

• Eslatma

• Shell saralash usulining yagona tavsifi har bir o‘tishdan keyin qadamlarni to‘g‘ri tanlashdan iborat.

• Qadamlarni tanlash:

• 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

• Def.

• Piramida deb balandligi k bo‘lgan shunday binar daraxtga aytiladiki, bunda
• k-1 daraxt ideal muvozanatlangan;
• k-1 bosqich to‘la, k bosqich esa chapdan o‘nga tomon to‘latiladi.

• > piramida  i uchun (ai ≥ a2i ) (ai ≥ a2i +1 )

• Piramidani massiv ko‘rinishida tasvirlab olish maqsadga muvofiq bo‘ladi.

• Algoritm

• 1. Boshlang‘ich ketma-ketlikdan piramida shaklantiriladi.
• 2. Kirish va tayyor ketma-ketlik bitta massivda saqlanadi. Piramida boshini olamiz va tayyor ketma-ketlikka joylashtiramiz. Keyin qolgan elementlar uchun piramidani tiklaymiz. Mazkur jarayon barcha elementlar tugaguncha davom etiladi.

• Piramida qurishga misol

• Qadam

• Qadam

• Qadam

• Qadam

• Qadam

• Chiqish

• Piramidani saralash

• almashtirish

• almashtirish

• almashtirish

• almashtirish

• shakllantirish

• shakllantirish

• shakllantirish

• shakllantirish

• almashtirish

• shakllantirish

• almashtirish

• shakllantirish

• almashtirish

• shakllantirish

• almashtirish

• shakllantirish

• almashtirish

• Samaradorlik: T(n)=O(nlogn)

• Tez saralash (Quicksort)

• Algoritm g’oyasi

• Bu usul almashtirish usulidagi saralashga tegishli bo‘lib uning asosini kalitlarni tanlangan kalitga nisbatan almashtirish tashkil qiladi.

• Misol:

• Samaradorlik: T(n)=O(nlogn)

13-Mavzu bo‘yicha nazorat savollari

• 1. Shell saralashi
• 2. Piramida tushunchasi va uni qurish
• 3. Piramidasimon saralash
• 4. Tez saralash tushunchasi