Birləşmə ilə çeşidləmə

8.1 Birləşmə ilə sıralamanın tərifi

Birləşmə ilə sıralama (Merge Sort) — effektli, stabil və müqayisəli sıralama alqoritmidir, hansı ki "böl və idarə et" yanaşmasından istifadə edərək elementləri sıralayır. Alqoritm massivi iki hissəyə bölür, hər hissəni rekursiv olaraq sıralayır və sonra sıralanmış hissələri birləşdirərək tək bir sıralanmış massiv əldə edir.

İş prinsipi:

Bölmə:

• Əsas massivi iki hissəyə bölün ki, iki alt massiv əldə olunsun.
• Hər alt massiv üçün prosesi təkrarlayın, ta ki hər alt massiv tək elementdən (və ya boşdan) ibarət olana qədər.

Birləşdirmə:

• İki yan-yana olan alt massivi tək sıralanmış massivdə birləşdirin.
• Birləşdirmə prosesini təkrarlayın, ta ki tək sıralanmış massiv əldə olunana qədər.

Birləşmə ilə sıralamanın vaxt və yer mürəkkəbliyi

Vaxt mürəkkəbliyi:

• Ən pis halda: O(n log n)
• Orta halda: O(n log n)
• Ən yaxşı halda: O(n log n)

Yer mürəkkəbliyi:

O(n) — müvəqqəti alt massivləri saxlamaq üçün əlavə yaddaş tələb olunur.

8.2 Aşağıya doğru birləşmə metodu

Əsas ardıcıllıq rekursiv şəkildə yarılara bölünür, nə vaxta qədər ki 1 elementdən ibarət alt-ardıcıllıqlar əldə edirik. Alınan alt-ardıcıllıqlardan birləşmə metodu ilə sıralı cütlüklər formalaşdırırıq, daha sonra — sıralı dördlüklər və s. bu cür davam edir.

Ardıcıllığa baxaq:

Ardıcıllığı 2 yarıya bölürük (rekursiv, cütlüklər alınanadək).

Hər bir alt-ardıcıllığı birləşmə metodu ilə sıralayırıq və hazır ardıcıllıq alırıq.

8.3 Birləşmə ilə çeşidləmə alqoritminin həyata keçirilməsi

Bax burada bizə rekursiya lazım olacaq! Bu, əvvəlki ilə müqayisədə çox yaxşı və sürətli bir alqoritmdir. O, massivi iki yerə bölür, hər iki hissəni ayrı-ayrılıqda çeşidləyir, sonra isə çeşidlənmiş hissələri tez birləşdirir.

Onun həyata keçirilməsi təxminən belə görünür:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Massivin ortasını tapırıq
        left_half = arr[:mid]  # Massivi iki alt massıva bölürük
        right_half = arr[mid:]
        
        merge_sort(left_half)  # Sol tərəfi rekursiv olaraq çeşidləyirik
        merge_sort(right_half)  # Sağ tərəfi rekursiv olaraq çeşidləyirik
        
        i = j = k = 0
        
        # Çeşidlənmiş hissələrin birləşməsi
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
        
        # Qalan elementləri yoxlayırıq
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

# İstifadə nümunəsi:
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Çeşidlənmiş massiv:", sorted_arr)
# Çıxış: Çeşidlənmiş massiv: [3, 9, 10, 27, 38, 43, 82]

Əsas məqam əvvəlindədir:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2 # Massivin ortasını tapırıq
        left_half = arr[:mid] # Massivi iki alt massıva bölürük right_half = arr[mid:]
        
        merge_sort(left_half)  # Sol tərəfi rekursiv olaraq çeşidləyirik
        merge_sort(right_half)  # Sağ tərəfi rekursiv olaraq çeşidləyirik

Burada nə baş verir:

1. Massivin ortası tapılır
2. Massiv 2 hissəyə bölünür
3. Hər hissə ayrı-ayrılıqda çeşidlənir

Bu yanaşma alqoritmi xeyli sürətləndirir.