Merge Sort Algorithm

Birlashtirib saralash (Merge Sort) — bu eng mashhur saralash algoritmlaridan biri bo'lib, u "Bo'lib ol va hukmronlik qil" (Divide and Conquer) tamoyiliga asoslanadi.

Bu usulda dastlabki masala bir nechta kichikroq qism-masalalarga ajratiladi. Har bir qism-masala alohida yechiladi. Yakunda qism-masalalarning yechimlari birlashtirilib, umumiy yakuniy yechim hosil qilinadi.

Birlashtirib saralash (Merge Sort) misoli

Divide and Conquer

"Bo'lib ol va hukmronlik qil" strategiyasi:

"Bo'lib ol va hukmronlik qil" usulida biz masalani uch bosqichda bajaramiz:

Faraz qilaylik, biz A massivini saralashimiz kerak. Qism-masala sifatida ushbu massivning p indeksidan boshlanib r indeksida tugaydigan qismini, ya'ni A[p..r] qism-massivini saralashni olamiz.

1. Bo'lish (Divide): Agar q indeksi p va r o'rtasidagi o'rta nuqta bo'lsa, biz A[p..r] massivini ikkita kichikroq qism-massivga ajratamiz: A[p..q] va A[q+1..r].

2. Hukmronlik qilish / Yechish (Conquer): Ushbu bosqichda ikkala A[p..q] va A[q+1..r] qism-massivlarni rekursiv tarzda saralaymiz. Agar tayanch holatga (1 ta elementli massivga) yetib bormagan bo'lsak, ularni yana ikkiga bo'lib saralashni davom ettiramiz.

3. Birlashtirish (Combine): Qism-massivlar bitta elementgacha bo'lingach, ular avtomatik saralangan hisoblanadi. Shundan so'ng, ikkita saralangan A[p..q] va A[q+1..r] qism-massivlarni birlashtirib, bitta kattaroq tartiblangan A[p..r] massivini hosil qilamiz.

Birlashtirib saralash algoritmi

MergeSort funksiyasi massivni toki 1 ta elementdan iborat bo'laklarga ajralguncha (p == r) muttasil ikkiga bo'lib boradi.

Shundan so'ng merge funksiyasi ishga tushadi va kichik tartiblangan massivlarni kattaroq tartiblangan massivlarga birlashtirib boradi:

MergeSort(A, p, r):
    if p >= r 
        return
    q = (p + r) / 2
    mergeSort(A, p, q)
    mergeSort(A, q + 1, r)
    merge(A, p, q, r)

Butun massivni saralash uchun MergeSort(A, 0, length(A) - 1) ko'rinishida chaqiriladi.

Birlashtirib saralash jarayonining vizual sxemasi

The Merge Step

Birlashtirish bosqichi:

Har qanday rekursiv algoritm tayanch holatga (base case) va uning natijalarini birlashtirish qobiliyatiga tayanadi. Birlashtirib saralash algoritmining eng muhim qismi — bu birlashtirish (merge) bosqichidir.

Birlashtirish bosqichi ikkita allaqachon saralangan massivni bitta katta saralangan massivga aylantirish masalasini hal qiladi.

Algoritm uchta ko'rsatkichdan (pointers) foydalanadi: ikkitasi har bir qism-massivdagi joriy elementni ko'rsatib turadi, uchinchisi esa yakuniy saralangan massivning joriy indeksini bildiradi.

Qaysidir massivning oxiriga yetib keldikmi?
    Yo'q:
        Ikkala massivning joriy elementlarini taqqoslaymiz
        Kichikroq elementni saralangan massivga ko'chiramiz
        Kichikroq element joylashgan massiv ko'rsatkichini bir qadam oldinga suramiz
    Ha:
        Tugamagan ikkinchi massivning qolgan barcha elementlarini saralangan massiv oxiriga to'g'ridan-to'g'ri ko'chiramiz

Ikkita saralangan massivni bitta massivga birlashtirish bosqichi

Birlashtirish funksiyasining bosqichma-bosqich ishlashi

Keling, amaliy misol orqali tahlil qilaylik:

Ikkita tutash qism-massiv: A[0..3] va A[4..5]

Massiv A[0..5] ikkita tartiblangan A[0..3] va A[4..5] qism-massivlardan iborat.

1-qadam: Saralanadigan qism-massivlarning nusxalarini yaratish

int n1 = q - p + 1 = 3 - 0 + 1 = 4;
int n2 = r - q = 5 - 3 = 2;

int L[4], M[2];
// L = [1, 5, 10, 12]
// M = [6, 9]

Birlashtirish uchun L va M nusxa massivlarini hosil qilish

2-qadam: Qism-massivlar va asosiy massiv indekslarini belgilash

int i = 0, j = 0, k = p;

Indekslar ko'rsatkichlarini boshlang'ich pozitsiyalarga qo'yish

3-qadam: L yoki M ning oxiriga yetguncha kichik elementni asosiy massivga ko'chirish

while (i < n1 && j < n2) {
    if (L[i] <= M[j]) {
        arr[k] = L[i];
        i++;
    } else {
        arr[k] = M[j];
        j++;
    }
    k++;
}

Taqqoslab, kichik elementlarni asosiy massivga ketma-ket joylashtirish

4-qadam: Qolib ketgan elementlarni ko'chirib o'tkazish

L yoki M qism-massivlaridan birortasidagi elementlar tugab qolsa, ikkinchi massivdagi qolgan barcha elementlar asosiy massiv oxiriga joylanadi:

Birinchi massivdan qolgan elementlarni asosiy massivga ko'chirish

Ikkinchi massivdan qolgan elementlarni ko'chirish

Birlashtirish funksiyasi yakunlangach, butun A[p..r] qismi to'liq saralangan bo'ladi.

Dasturiy namunalar

// Go tilida Merge Sort algoritmi
package main

import "fmt"

// Ikki qism-massivni birlashtirish
func merge(arr []int, p, q, r int) {
	n1 := q - p + 1
	n2 := r - q

	L := make([]int, n1)
	M := make([]int, n2)

	for i := 0; i < n1; i++ {
		L[i] = arr[p+i]
	}
	for j := 0; j < n2; j++ {
		M[j] = arr[q+1+j]
	}

	i, j, k := 0, 0, p

	for i < n1 && j < n2 {
		if L[i] <= M[j] {
			arr[k] = L[i]
			i++
		} else {
			arr[k] = M[j]
			j++
		}
		k++
	}

	// L dagi qolgan elementlar
	for i < n1 {
		arr[k] = L[i]
		i++
		k++
	}

	// M dagi qolgan elementlar
	for j < n2 {
		arr[k] = M[j]
		j++
		k++
	}
}

// Birlashtirib saralash funksiyasi
func mergeSort(arr []int, l, r int) {
	if l < r {
		m := l + (r-l)/2

		mergeSort(arr, l, m)
		mergeSort(arr, m+1, r)

		merge(arr, l, m, r)
	}
}

func main() {
	arr := []int{6, 5, 12, 10, 9, 1}
	fmt.Println("Dastlabki massiv:", arr)

	mergeSort(arr, 0, len(arr)-1)

	fmt.Println("Saralangan massiv:", arr)
}

Birlashtirib saralashning murakkabligi

Birlashtirib saralash har qanday kiruvchi ma'lumotda kafolatlangan O(n log n) vaqt murakkabligiga ega bo'lib, uning barqarorligi bir xil qiymatga ega elementlar tartibini o'zgartirmay saqlab qoladi.

Birlashtirib saralashning qo'llanilishi

• Inversiyalar sonini hisoblash masalalarida (Inversion count problem): Massiv qanchalik tartibsiz ekanligini o'lchashda.
• Tashqi saralashda (External sorting): Ma'lumotlar hajmi operativ xotiraga (RAM) sig'magan hollarda (fayllar va disklardagi ulkan ma'lumotlarni saralashda).
• Elektron tijorat (E-commerce) ilovalarida: Qidiruv natijalarini turli mezonlar bo'yicha barqaror saralashda.