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

Qulaylik va ravshanlik uchun bitta guruh elementlari bir xil rangda ko‘rsatilgan.


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

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)
  

Tez saralash (Quicksort)
Misol:
Samaradorlik: T(n)=O(nlogn)

Samaradorligi :

• 
  Yaxshi holat. Har bir iteratsiyada massiv 2ta teng podmassivga bo’linadi.Bu saralash uchun eng kam vaqtni beradi. Bunda – O(n2)
  
• 
  Yomon holat. Har bir iteratsiyada massiv 1ta tayanch elementdan iborat podmassiv va qolgan barcha elementdan iborat podmassivga bo’linadi. Bu xolat har bir etapda yoki eng kichik yoki eng katta element tanlanganda yuz beradi. –
  

  О(n logn)

• 
  O’rtacha samaradorlik - О(n logn).
  

Birlashtirish orqali saralash (sortirovka sliyaniyem)

Saralash masalasini hal qilish bosqichlari:

• 
  Saralanadigan massiv ikkita kichik qismga bo'linadi;
  
• 
  Olingan qismlarning har biri alohida tartiblanadi;
  
• 
  Kichik o'lchamdagi ikkita tartiblangan massiv bittaga birlashtiriladi(tanlash orqali).
  

  Masalani kichik qismlarga rekursiv bo'linish massivning o’lchami bir kattalikda bo'lguncha sodir bo'ladi (1 uzunlikdagi har qanday massivni tartiblangan deb hisoblash mumkin).

Birlashtirish orqali saralash

Birlashtirish orqali saralash
Mavzu bo‘yicha nazorat savollari

• 
  Shell saralashi
  
• 
  Sheyker saralashi
  
• 
  Tez saralash tushunchasi
  
• 
  Birlashtirish orqali saralash
  

E’tiboringiz uchun raxmat !!!

http://azkurs.org