Sortowanie przez scalanie

8.1 Definicja sortowania przez scalanie

Sortowanie przez scalanie (Merge Sort) to efektywny, stabilny i porównawczy algorytm sortowania, który wykorzystuje podejście "dziel i zwyciężaj" do uporządkowania elementów. Algorytm dzieli tablicę na dwie połowy, rekursywnie sortuje każdą połowę, a następnie scala posortowane połowy w jedną posortowaną tablicę.

Zasada działania:

Podział:

• Podziel oryginalną tablicę na pół, aby uzyskać dwa podtablice.
• Powtarzaj proces dla każdej podtablicy, aż każda podtablica stanie się tablicą z jednym elementem (lub pustą).

Scalanie:

• Scalaj dwie sąsiednie podtablice w jedną posortowaną tablicę.
• Powtarzaj proces scalania, aż uzyskasz jedną posortowaną tablicę.

Wskaźnik czasowy i przestrzenny sortowania przez scalanie

Wskaźnik czasowy:

• W najgorszym przypadku: O(n log n)
• W średnim przypadku: O(n log n)
• W najlepszym przypadku: O(n log n)

Wskaźnik przestrzenny:

O(n) — dodatkowa pamięć niezbędna do przechowywania tymczasowych podtablic.

8.2 Metoda scalania od góry w dół

Oryginalna sekwencja jest rekursywnie dzielona na połowy, aż uzyskamy podciągi po 1 elemencie. Z uzyskanych podciągów formujemy uporządkowane pary metodą scalania, następnie — uporządkowane czwórki i tak dalej.

Przeanalizujmy sekwencję:

Dzielimy sekwencję na 2 połowy (rekursywnie, aż uzyskamy pary).

Każdy podciąg porządkujemy metodą scalania i uzyskujemy gotową sekwencję.

8.3 Implementacja algorytmu sortowania przez scalanie

I tu przyda się nam rekurencja! To jest naprawdę dobry i szybki algorytm w porównaniu do poprzednich. Dzieli tablicę na pół, sortuje obie części osobno, a następnie szybko łączy posortowane części.

Wygląda na to, że jego implementacja wygląda mniej więcej tak:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Znajdujemy środek tablicy
        left_half = arr[:mid]  # Dzielimy tablicę na dwa podtablice
        right_half = arr[mid:]
        
        merge_sort(left_half)  # Rekursywnie sortujemy lewą połowę
        merge_sort(right_half)  # Rekursywnie sortujemy prawą połowę
        
        i = j = k = 0
        
        # Scalanie posortowanych połówek
        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
        
        # Sprawdzanie pozostałych elementów
        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

# Przykład użycia:
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Posortowana tablica:", sorted_arr)
# Wyjście: Posortowana tablica: [3, 9, 10, 27, 38, 43, 82]

Kluczowy moment na początku:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2 # Znajdujemy środek tablicy
        left_half = arr[:mid] # Dzielimy tablicę na dwa podtablice right_half = arr[mid:]
        
        merge_sort(left_half)  # Rekursywnie sortujemy lewą połowę
        merge_sort(right_half)  # Rekursywnie sortujemy prawą połowę

Oto, co się tu dzieje:

1. Znajdujemy środek tablicy
2. Dzielimy tablicę na 2 części
3. Sortujemy każdą część osobno

Takie podejście bardzo przyspiesza algorytm.