Birlashmali saralash (Merge Sort)
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
).
Java dasturlash tilidagi algoritm kodi:
import java.util.Arrays; public class MergeSort { public static void main(String[] args) { int[] A = {6,5,12,10,9,1}; sort(A); //saralashni boshlash System.out.println(Arrays.toString(A)); //natijani chop qilish } private static void sort(int[] array) { if(array.length0){ if (leftIndex >= left.length){ array[targetIndex] = right[rightIndex++]; }else if (rightIndex >= right.length){ array[targetIndex] = left[leftIndex++]; }else if (left[leftIndex]-right[rightIndex]Qadamlarda tasvirlanishi:
Aytib o`tish joizki, chiziqli saralash algoritmlaridan farqli o`laroq, birlashmali saralash massiv avvaldan saralangan yoki saralanmaganligiga qaramay ajratib birlashtiradi. Shuning uchun ham eng yomon holatda, u chiziqli saralash algoritmlariga qaraganda tez ishlashiga qaramay, eng yaxshi holatda uning samarasi chiziqli algoritmlardan past bo`ladi. Demak, birlashmali saralashni qisman saralangan massivlarni saralash uchun qo`llamagan ma'qul.
Birlashmali saralashning boshqa saralash algoritmlari bilan solishtirish:
Algoritm |
Eng yaxshi |
O`rtacha |
Eng yomon |
Tanlab saralash | O(n^2) | O(n^2) | O(n^2) |
Pufakchali saralash | O(n) | O(n^2) | O(n^2) |
Tezkor saralash | O(n log(n)) | O(n log(n)) | O(n^2) |
Birlashmali saralash | O(n log(n)) | O(n log(n)) | O(n log(n)) |
Jadvaldan ko`rinib turibdiki, umumiy holatda birlashmali saralash algoritmidan foydalanish samaraliroq hisoblanadi.
Algoritm
Birlashmali saralash (Merge Sort)