“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

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

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

1)Bu pufaksimon usulning takomillashtirilgan holidir.

2) Binar saralash daraxtini yani massiv elementlarini binary daraxt kabi tashkil etishni ko’zda tutadi.

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)

• Bu usul ingliz informatigi Charlz Xoar (Чарльз Хоар) tomonidan 1960 yilda Moskva universitetida kompiyterda electron tarjima qilish bo’yicha o’qiyotganida, rus-ingliz so’zlashgichini ishlab chiqayotganida taklif etilgan.

Bu usul almashtirish usulining modifikatsiyasi bo‘lib, uning asosini kalitlarni tanlangan kalitga(tayanch kalit) nisbatan almashtirish tashkil qiladi. Tanlash-ixtiyoriy ravishda, masalan, o’rtasini.

• Bu usul almashtirish usulining modifikatsiyasi bo‘lib, uning asosini kalitlarni tanlangan kalitga(tayanch kalit) nisbatan almashtirish tashkil qiladi. Tanlash-ixtiyoriy ravishda, masalan, o’rtasini.
• Algoritm g’oyasi: 1) tayanch element tanlanadi;
• 2) elementlarni tayanch elementdan kichik elementlar to’plami va katta yoki teng elementlar to’plamiga bo’lamiz;
• 3) bu 2 to’plamga nisbatan yuqoridagi 1-2 punktni qo’llaymiz ( bo’sh yoki 1ta elementli to’plamga qo’llanilmaydi)