Samouczek algorytmu sortowania przez scalanie w Pythonie

Dowiedz się, jak zaimplementować sortowanie przez scalanie w Pythonie. Interaktywny przykład strategii sortowania „Dziel i zwyciężaj” krok po kroku.

Spróbuj w Edytorze

Przegląd

Sortowanie przez scalanie to bardzo wydajny algorytm sortowania wykorzystujący strategię dziel i zwyciężaj. Dzieli nieposortowaną listę na mniejsze podlisty, sortuje te podlisty, a następnie ponownie je łączy.

Algorytm rekurencyjnie dzieli tablicę na pół, aż osiągnie jednoelementowe podtablice. Następnie łączy posortowane podtablice, porównując elementy z każdej strony i umieszczając je w posortowanej kolejności. Zapewnia to optymalną złożoność czasową.

Niezależnie od tego, czy początkowa tablica jest posortowana, odwrócona, czy całkowicie losowa, sortowanie przez scalanie jest wykonywane w czasie O(n log n). Wymaga to jednak O(n) dodatkowej przestrzeni do przechowywania list podrzędnych podczas fazy łączenia.

Dane wyjściowe kodu i wykonania

Standardowa rekurencyjna implementacja algorytmu sortowania przez scalanie w Pythonie.

merge_sort.py

Spróbuj w Edytorze

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
        
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    
    return merge(left_half, right_half)

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

# Test dataset
data = [38, 27, 43, 3, 9, 82, 10]
print("Original List:", data)
sorted_data = merge_sort(data)
print("Sorted List:  ", sorted_data)

Wyjście terminala

Original List: [38, 27, 43, 3, 9, 82, 10]
Sorted List:   [3, 9, 10, 27, 38, 43, 82]

Wdrażanie krok po kroku

Sortowanie połączonych list, gdzie struktura węzłów ułatwia łatwe łączenie bez kopiowania
Zewnętrzne procedury sortowania plików, które nie mieszczą się całkowicie w systemowej pamięci RAM
Stabilne aplikacje sortujące, w których pasujące klucze muszą zachować swoją pierwotną kolejność

Często zadawane pytania

Czy sortowanie przez scalanie jest stabilnym algorytmem sortowania?

Tak, sortowanie przez scalanie jest stabilne. Podczas porównywania identycznych elementów element z lewej (oryginalnej pierwszej) podtablicy jest umieszczany jako pierwszy, zachowując swoje pierwotne względne położenie.

Dlaczego Python używa Timsort zamiast czystego sortowania przez scalanie?

Wbudowana w Pythonie funkcja „sorted()” wykorzystuje Timsort, który jest algorytmem hybrydowym łączącym sortowanie przez scalanie i sortowanie przez wstawianie. Optymalizuje wzorce danych w świecie rzeczywistym, identyfikując już posortowane podsegmenty, dzięki czemu są one szybsze niż zwykłe sortowanie przez scalanie.

Powiązane tematy

Przewodnik po algorytmie szybkiego sortowania w języku Python

Poznaj algorytm szybkiego sortowania w Pythonie. Naucz się selekcji przestawnej, partycjonowania i rekurencji w tym interaktywnym przykładzie kodowania.

Algorytmy sortowania w Pythonie

Poznaj algorytmy sortowania w Pythonie. Wizualizuj sortowanie bąbelkowe i sortowanie przez scalanie natywnie w kontekście IDE przeglądarki.

Algorytm wyszukiwania binarnego w Pythonie

Przeszukuj posortowane listy w logarytmicznym czasie O(log n). Uruchom i zrozum wyszukiwanie binarne w Pythonie, w tym logikę krok po kroku, przypadki brzegowe i optymalizacje.