DSA Merge Sort (birlashtirib saralash)

Merge Sort

Merge Sort algoritmi — "bo‘lib tashla va hukmronlik qil" (divide-and-conquer) turidagi algoritm bo‘lib, u massivni avval kichikroq massivlarga ajratib, so‘ngra massivni saralangan bo‘ladigan qilib to‘g‘ri tarzda qayta yig‘ish orqali saralaydi.

Bo‘lish (Divide): Algoritm massivni qism massivlardan biri faqat bitta elementdan iborat bo‘lib qolguncha tobora kichikroq bo‘laklarga ajratishdan boshlanadi.

Yengish (Conquer): Algoritm massivning kichik bo‘laklarini eng kichik qiymatlarni birinchi qo‘yib, qayta birlashtiradi va natijada saralangan massiv hosil bo‘ladi.

Massivni saralash uchun uni bo‘laklarga ajratish va qayta yig‘ish rekursiv ravishda bajariladi.

Yuqoridagi animatsiyada ustunlarning har safar pastga tushirilishi massivni kichikroq bo‘laklarga ajratuvchi rekursiv chaqiruvni ifodalaydi. Ustunlar yuqoriga ko‘tarilganda esa bu ikkita qism massiv birlashtirilganini bildiradi.

Merge Sort algoritmini quyidagicha tavsiflash mumkin:

Merge Sort qanday ishlashini boshqa nuqtai nazardan ko‘rish uchun quyidagi chizmaga qarang. Ko‘rib turganingizdek, massiv qayta birlashtirilgunga qadar tobora kichikroq bo‘laklarga bo‘linadi. Birlashtirish jarayonida esa eng kichik qiymat birinchi kelishi uchun har bir qism massivdagi qiymatlar taqqoslanadi.

Qo‘lda bajarib ko‘rish

Merge Sort’ni dasturlash tilida amalda amalga oshirishdan oldin, u qanday ishlashini yanada yaxshiroq tushunib olish uchun saralashni qo‘lda bajarib ko‘raylik.

1-qadam: Saralanmagan massivdan boshlaymiz va u qism massivlar faqat bitta elementdan iborat bo‘lib qolguncha teng ikkiga bo‘linishini bilamiz. Merge Sort funksiyasi o‘zini ikki marta — massivning har bir yarmi uchun bir martadan chaqiradi. Bu birinchi qism massiv eng kichik bo‘laklarga birinchi bo‘lib bo‘linishini anglatadi.

2-qadam: Birinchi qism massivni bo‘lish yakunlandi, endi birlashtirish vaqti keldi. Birlashtiriladigan dastlabki ikkita element — 8 va 9. 8 eng kichik qiymat, shuning uchun birinchi birlashtirilgan qism massivda u 9 dan oldin keladi.

3-qadam: Navbatdagi birlashtiriladigan qism massivlar — [ 12] va [ 8, 9]. Ikkala massivdagi qiymatlar boshidan boshlab taqqoslanadi. 8 soni 12 dan kichik, shuning uchun 8 birinchi keladi, 9 ham 12 dan kichik.

4-qadam: Endi ikkinchi katta qism massiv rekursiv ravishda bo‘linadi.

5-qadam: 3 va 11 ko‘rsatilgan tartibda qayta birlashtiriladi, chunki 3 soni 11 dan kichik.

6-qadam: 5 va 4 qiymatli qism massiv bo‘linadi, so‘ngra 4 soni 5 dan oldin keladigan qilib birlashtiriladi.

7-qadam: O‘ng tomondagi ikkita qism massiv birlashtiriladi. Yangi birlashtirilgan massiv elementlarini hosil qilish uchun taqqoslashlar bajariladi:

1. 3 soni 4 dan kichik
2. 4 soni 11 dan kichik
3. 5 soni 11 dan kichik
4. 11 — qolgan oxirgi qiymat

8-qadam: Qolgan oxirgi ikkita qism massiv birlashtiriladi. Yangi birlashtirilgan va to‘liq saralangan massivni hosil qilish uchun taqqoslashlar qanday bajarilishini batafsilroq ko‘rib chiqaylik:

3 soni 8 dan kichik:

9-qadam: 4 soni 8 dan kichik:

10-qadam: 5 soni 8 dan kichik:

11-qadam: 8 va 9 sonlari 11 dan kichik:

12-qadam: 11 soni 12 dan kichik:

Saralash yakunlandi!

Yuqoridagi qadamlarni animatsiyada ko‘rish uchun quyidagi simulyatsiyani ishga tushiring:

{{ x.dieNmbr }}

Qo‘lda bajarib ko‘rish: nima sodir bo‘ldi?

Algoritm ikki bosqichdan iborat ekanini ko‘ramiz: avval bo‘lish, so‘ngra birlashtirish.

Merge Sort algoritmini rekursiyasiz amalga oshirish mumkin bo‘lsa-da, biz rekursiyadan foydalanamiz, chunki bu eng keng tarqalgan yondashuv.

Buni yuqoridagi qadamlarda ko‘ra olmaymiz, ammo massivni ikkiga bo‘lish uchun massiv uzunligi ikkiga bo‘linadi va so‘ngra pastga yaxlitlanib, biz "mid" deb ataydigan qiymat olinadi. Bu "mid" qiymati massivni qayerdan bo‘lish kerakligini ko‘rsatuvchi indeks sifatida ishlatiladi.

Massiv bo‘lingandan so‘ng, uni yana rekursiv ravishda bo‘lish mumkin bo‘lishi uchun saralash funksiyasi har bir yarmi bilan o‘zini o‘zi chaqiradi. Qism massiv faqat bitta elementdan iborat bo‘lib qolganda bo‘lish to‘xtaydi.

Merge Sort funksiyasi oxirida qism massivlar shunday birlashtiriladiki, massiv qayta yig‘ilayotganda qism massivlar doimo saralangan bo‘ladi. Natija saralangan bo‘lishi uchun ikkita qism massivni birlashtirishda har bir qism massivning qiymatlari taqqoslanadi va eng kichik qiymat birlashtirilgan massivga qo‘yiladi. Shundan so‘ng ikkala qism massivdagi navbatdagi qiymatlar taqqoslanadi va ulardan eng kichigi birlashtirilgan massivga qo‘yiladi.

Merge Sort’ni amalga oshirish

Merge Sort algoritmini amalga oshirish uchun bizga quyidagilar kerak:

1. Saralanishi kerak bo‘lgan qiymatlarga ega massiv.
2. Massivni qabul qilib, uni ikkiga bo‘ladigan va massivlar qism massiv faqat bitta qiymatdan iborat bo‘lib qolguncha rekursiv ravishda qayta-qayta bo‘linishi uchun shu massivning har bir yarmi bilan o‘zini o‘zi chaqiradigan funksiya.
3. Qism massivlarni saralangan holda qayta birlashtiradigan boshqa funksiya.

Natijaviy kod quyidagicha ko‘rinadi:

def mergeSort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    leftHalf = arr[:mid]
    rightHalf = arr[mid:]

    sortedLeft = mergeSort(leftHalf)
    sortedRight = mergeSort(rightHalf)

    return merge(sortedLeft, sortedRight)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])

    return result

unsortedArr = [3, 7, 6, -10, 15, 23.5, 55, -13]
sortedArr = mergeSort(unsortedArr)
print("Sorted array:", sortedArr)

6-qatorda arr[:mid] massivdan "mid" indeksidagi qiymatgacha bo‘lgan (uning o‘zini hisobga olmagan holda) barcha qiymatlarni oladi.

7-qatorda arr[mid:] massivdan "mid" indeksidagi qiymatdan boshlab, undan keyingi barcha qiymatlarni oladi.

26-27-qatorlarda birlashtirishning birinchi qismi allaqachon bajarilgan bo‘ladi. Bu nuqtada ikkala qism massiv qiymatlari taqqoslab bo‘lingan va chap yoki o‘ng qism massivdan biri bo‘sh bo‘ladi, shuning uchun natijaviy massivni chap yoki o‘ng qism massivda qolgan qiymatlar bilan shunchaki to‘ldirish mumkin. Bu qatorlarning o‘rnini almashtirish mumkin, natija bir xil bo‘ladi.

Rekursiyasiz Merge Sort

Merge Sort "bo‘lib tashla va hukmronlik qil" turidagi algoritm bo‘lgani uchun uni amalga oshirishda rekursiyadan foydalanish eng intuitiv yo‘ldir. Merge Sort’ning rekursiv amalga oshirilishi, ehtimol, tushunish uchun ham osonroq va umuman olganda kamroq kod qatorini talab qiladi.

Ammo Merge Sort’ni rekursiyadan foydalanmasdan ham, ya’ni o‘zini o‘zi chaqiradigan funksiyasiz ham amalga oshirish mumkin.

Rekursiyadan foydalanmaydigan quyidagi Merge Sort amalga oshirilishiga qarang:

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
            
    result.extend(left[i:])
    result.extend(right[j:])
    
    return result

def mergeSort(arr):
    step = 1  # Starting with sub-arrays of length 1
    length = len(arr)
    
    while step < length:
        for i in range(0, length, 2 * step):
            left = arr[i:i + step]
            right = arr[i + step:i + 2 * step]
            
            merged = merge(left, right)
            
            # Place the merged array back into the original array
            for j, val in enumerate(merged):
                arr[i + j] = val
                
        step *= 2  # Double the sub-array length for the next iteration
        
    return arr

unsortedArr = [3, 7, 6, -10, 15, 23.5, 55, -13]
sortedArr = mergeSort(unsortedArr)
print("Sorted array:", sortedArr)

Yuqoridagi ikkala Merge Sort amalga oshirilishida merge funksiyalari aynan bir xil ekanini payqagandirsiz, ammo aynan shu yerning tepasidagi amalga oshirilishda rekursiya o‘rniga mergeSort funksiyasi ichidagi while siklidan foydalanilgan. While sikli massivni joyida (in place) bo‘lish va birlashtirishni bajaradi, bu esa kodni tushunishni biroz qiyinlashtiradi.

Soddaroq qilib aytganda, mergeSort funksiyasi ichidagi while sikli merge funksiyasi yordamida dastlabki massivning mayda bo‘laklarini (qism massivlarini) saralash uchun qisqa qadam uzunliklaridan foydalanadi. So‘ngra butun massiv saralanguncha massivning kattaroq bo‘laklarini birlashtirish va saralash uchun qadam uzunligi oshiriladi.

Merge Sort’ning vaqt murakkabligi

Vaqt murakkabligi nima ekanligi haqida umumiy tushuntirish uchun ushbu sahifaga tashrif buyuring.

Merge Sort vaqt murakkabligi haqida yanada chuqurroq va batafsil tushuntirish uchun ushbu sahifaga tashrif buyuring.

Merge Sort’ning vaqt murakkabligi

\[ O( n \cdot \log n ) \]

Vaqt murakkabligi turli xil massivlar uchun deyarli bir xil. Massiv allaqachon saralangan yoki butunlay aralashtirilgan bo‘lishidan qat’i nazar, algoritm uni bo‘lishi va qayta birlashtirishi kerak.

Quyidagi rasmda Merge Sort’ning vaqt murakkabligi ko‘rsatilgan.

Quyidagi simulyatsiyani massivdagi qiymatlarning turli sonlari uchun ishga tushiring va Merge Sort’ga \(n\) ta elementli massiv uchun kerak bo‘ladigan amallar soni qanday qilib \(O(n \log n)\) ga teng ekanini ko‘ring:

Agar qiymatlar soni \(n\) ni o‘zgarmas qoldirsak, "Tasodifiy", "Kamayish tartibida" va "O‘sish tartibida" variantlari uchun kerak bo‘ladigan amallar soni deyarli bir xil bo‘ladi.

Merge Sort har safar deyarli bir xil ishlaydi, chunki massiv allaqachon saralangan bo‘lsa ham, bo‘lmasa ham, u bo‘linadi va taqqoslash yordamida birlashtiriladi.