Fakulteti kafedrasi


Amaliy bo’lmagan saralash


Download 0.72 Mb.
bet6/7
Sana12.11.2021
Hajmi0.72 Mb.
1   2   3   4   5   6   7
Amaliy bo’lmagan saralash

1. Bogosort – algoritm murakkabligi O(n n!).

2. O’rinlashtirish saralash – algoritm murakkabligi O(n n!).

3. Ma’nosiz saralash (Stupid sort) – algoritm murakkabligi O(n3).

4. Bead asort – Algoritm murakkabligi O(n) yoki O(sqrt(n)).

Maxsus apparat taminoti talab etiladi.

5.Quymoqli saralash (Pancake sorting) – Algoritm murakkabligi O(n).

Maxsus apparat taminoti talab etiladi.

Ko’rib turubsiz saralash algaritimlari juda ko’p turlari mavjud. Shulardan bazi

birlari birlari bilan tanishib chiqamiz.



Qiyin, lekin samarali usullar


  1. «tezsaralash» (Quick Sort)


  2. «to’p-to’p» saralash (Heap Sort)


  3. Qo’shilib saralash


  4. Piramidali saralash

Algaritm murakkabligi O(N*logN)



Birlashmali saralash (Merge Sort)

Bu algoritm Jon Fon Neyman tamonidan 1946 yilda taklif qilingan.

Jon Fon Neyman Vengriyalik matematika, kvant fizikasi, funksional analiz,to’plamlar nazariyasi, ekonomika, informatika kabi fanlarga munosib hissa qo’shgan.






Birlashmali saralash (Merge Sort) algoritmi asosiy beshta saralash algoritmlari (pufakchali saralash, tezkor saralash va boshqalar) dan biri bo`lib, chiziqli saralash algoritmlaridan farqli ravishda "bo`lib tashla va hukmronlik qil" tipidagi algoritm hisoblanadi.

Bu tipdagi algoritmlar katta hajmdagi masalalarni nisbatan kichik bo`lgan va oson yechiladigan qismlarga ajratgan holda bajaradi. Bunday algoritmlar masalalarni hal qilishda vaqtdan katta yutuq qilish imkonini beradi.

Birlashmali saralashda biz berilgan massivni uzunligi faqat 1 elementga teng bo`lgan qismlar qolmaguncha o`rtasidan ajratamiz. Keyin bu qismlar to`g`ri tartibda birlashtiriladi.

Keling ushbu massivni qaraylik:



Uni teng ikkiga ajratamiz:



Va yana har bir qismni ikkiga ajratamiz, toki 1 elementli qismlar qolmagunicha:



Massivni maksimal qisqa qismlarga ajratgandan so`ng, ularni to`g`ri tartibda birlashtiramiz, ya'ni:



Dastlab, 2 elementli saralangan guruhlarni olamiz va ularni 4 elementli guruhlarga birlashtiramiz va yakunida hammasini birlashtirgan holda saralangan massivni hosil qilamiz.



Algoritm ishlashi uchun quyidagi amallarni amalga oshirish kerak:

Massivni guruhlarga rekursiv ajratish amali ( sort).

To`g`ri tartibda birlashtirish amali (merge). 




Download 0.72 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2020
ma'muriyatiga murojaat qiling