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:

data_structures_047

Uni teng ikkiga ajratamiz:

data_structures_048

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

data_structures_049

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

data_structures_050

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

data_structures_051

Algoritm ishlashi uchun quyidagi amallarni amalga oshirish kerak:

  1. Massivni guruhlarga rekursiv ajratish amali ( sort).
  2. 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.length<=1){ //massiv qismlarini elementlar sonin aniqlash 
            return;          //1 dan kichik yoki teng bo`lsa ajratishni to`xtatish
        }
        int leftSize = array.length/2;          //chap tomon bo`lak uzunligini aniqlash
        int rightSize = array.length-leftSize;  //o`ng tomon bo`lak uzunligini aniqlash
        int[] left = Arrays.copyOfRange(array, 0, leftSize);                      //mos ravishda o`ng va chap
        int[] right = Arrays.copyOfRange(array, leftSize, leftSize+rightSize);    //submassivlarga ajratish
        sort(left);   //rekursiya orqali
        sort(right);  //bo`laklarga ajratish
        merge(array, left, right);  //to`g`ri tartibda birlashtirish
    }
    private static void merge(int[] array, int[] left, int[] right) {
        int leftIndex = 0;        //left va right submassiv elementlarini
        int rightIndex = 0;       //to`g`ri saralangan tartibda
        int targetIndex = 0;      //array massiviga joylashtirsh
        int remaining = left.length+right.length;       
        while(remaining>0){                               
            if (leftIndex >= left.length){
                array[targetIndex] = right[rightIndex++];
            }else 
                if (rightIndex >= right.length){
                    array[targetIndex] = left[leftIndex++];
                }else 
                    if (left[leftIndex]-right[rightIndex] < 0){
                        array[targetIndex] = left[leftIndex++];
                    }else{
                        array[targetIndex] = right[rightIndex++];
                    }
            targetIndex++;
            remaining--;
        }
    }
}

Qadamlarda tasvirlanishi:

merge sort example

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.


SabirovTemurbek

Muallif haqida

SabirovTemurbek


Blogdagi so‘nggi maqolalar:


Fikrlar 4

abdujabbor1987
abdujabbor1987
Juda yaxshi maqola bo'libti! avtorga katta rahmat! bir savol bor, quick sort aynan qaysi xolatda O(n ^ 2) bilan ishlaydi?
SabirovTemurbek
SabirovTemurbek
1 9 5 13 3 11 7 15 2 10 6 14 4 12 8 16 Shu eng yomon ko'p amal bajaradigan variant u O(n*logn) da ishlaydi O(n^2) da emas
ulugbekrozimboyev
ulugbekrozimboyev
menda `go` da yozilgan kodi bor ekan, kimgadir qiziq bo'lsa agar: https://github.com/ulugbekrozimboyev/learn-algoritms/blob/master/merge_sort.go juda yaxshi yozilgan deya olmayman
ulugbekrozimboyev
ulugbekrozimboyev
yaxshi maqola uchun muallifga rahmat
Iltimos, fikr bildirish uchun saytga kiring yoki ro‘yxatdan o‘ting!