Ten blog opiera się na podejściu dziel i rządź. Merge Sort to algorytm „dziel i rządź”, w którym problem jest dzielony na podproblemy, a następnie scalany w celu pokonania rozwiązania. Ten blog o scalaniu Sortuj w szczegółowo przeprowadzi Cię przez poniższe tematy -
- Co to jest sortowanie przez scalanie w Pythonie?
- Podejście Dziel i rządź
- Implementacja sortowania przez scalanie w Pythonie
- Schemat blokowy implementacji sortowania przez scalanie
- Zalety i zastosowanie
Co to jest sortowanie przez scalanie w Pythonie?
Sortowanie przez scalanie jest oparte na algorytmie dziel i zwyciężaj, w którym tablica wejściowa jest dzielona na dwie połowy, a następnie sortowana oddzielnie i łączona z powrotem w celu uzyskania rozwiązania. Funkcja merge () służy do scalania posortowanych .
Podejście Dziel i rządź
- Macierz jest dzielona na pół i proces jest powtarzany z każdą połową, aż każda połowa będzie miała rozmiar 1 lub 0.
- Tablica o rozmiarze 1 jest posortowana w trywialny sposób.
- Teraz dwie posortowane tablice są łączone w jedną dużą tablicę. I jest to kontynuowane, aż wszystkie elementy zostaną połączone i tablica zostanie posortowana.
Oto wizualizacja sortowania przez scalanie, aby wyczyścić obraz
java system.exit (1)
Tablica wejściowa = [3,1,4,1,5,9,2,6,5,4]
Przejdźmy teraz do realizacji.
Implementacja sortowania przez scalanie w Pythonie
def mergeSort (nlist): print ('Splitting', nlist) if len (nlist)> 1: mid = len (nlist) // 2 lefthalf = nlist [: mid] righthalf = nlist [mid:] mergeSort (lefthalf) mergeSort (righthalf) i = j = k = 0, a i Wynik:
$ python main.py
(„Podział”, [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
(„Splitting”, [3, 1, 4, 1, 5])
(„Splitting”, [3, 1])
(„Splitting”, [3])
(„Merging”, [3])
(„Splitting”, [1])
(„Merging”, [1])
(„Merging”, [1, 3])
(„Splitting”, [4, 1, 5])
(„Splitting”, [4])
(„Merging”, [4])
(„Splitting”, [1, 5])
(„Splitting”, [1])
(„Merging”, [1])
(„Splitting”, [5])
(„Merging”, [5])
(„Merging”, [1, 5])
(„Merging”, [1, 4, 5])
(„Merging”, [1, 1, 3, 4, 5])
(„Splitting”, [9, 2, 6, 5, 4])
(„Splitting”, [9, 2])
(„Splitting”, [9])
(„Merging”, [9])
(„Splitting”, [2])
(„Merging”, [2])
(„Merging”, [2, 9])
(„Splitting”, [6, 5, 4])
(„Splitting”, [6])
(„Merging”, [6])
(„Splitting”, [5, 4])
(„Splitting”, [5])
(„Merging”, [5])
(„Splitting”, [4])
(„Merging”, [4])
(„Merging”, [4, 5])
(„Merging”, [4, 5, 6])
(„Merging”, [2, 4, 5, 6, 9])
(„Merging”, [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]
dyplom podyplomowy vs tytuł magistra
Schemat blokowy implementacji sortowania przez scalanie
Zalety i wykorzystanie sortowania przez scalanie
Większość pozostałych algorytmów działa źle z sekwencyjnymi strukturami danych, takimi jak pliki i połączone listy. W tych strukturach dostęp do elementu losowego wymaga czasu liniowego, a nie regularnego stałego czasu. Charakter sortowania przez scalanie ułatwia i przyspiesza tworzenie takich struktur danych.Jedną z najlepszych cech sortowania przez scalanie jest niewielka liczba porównań. Daje O (n * log (n)) liczbę porównań, ale stały współczynnik jest dobry w porównaniu do szybkiego sortowania, co czyni go użytecznym, gdy funkcja porównania jest powolną operacją.Ponadto podejście typu „podziel i zwyciężaj” w sortowaniu przez scalanie ułatwia przetwarzanie równoległe.
W ten sposób kończymy blog poświęcony „Jak zaimplementować sortowanie przez scalanie w Pythonie”. Mam nadzieję, że zawartość dodała trochę wartości do twojej wiedzy w Pythonie. Aby uzyskać dogłębną wiedzę na temat języka Python i jego różnych aplikacji, możesz zarejestrować się na żywo z całodobowym wsparciem i dożywotnim dostępem.