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:

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:

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:

Jadvaldan ko`rinib turibdiki, umumiy holatda birlashmali saralash algoritmidan foydalanish samaraliroq hisoblanadi.