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).
Birlashmali saralashning boshqa saralash algoritmlari bilan solishtirish:
Dostları ilə paylaş: |
