Sortowanie przez scalanie w Pythonie

powrót

Sortowanie przez scalanie należy do algorytmów, które wykorzystują technikę "dziel i zwyciężaj". Złożoność algorytmu wynosi $$n\cdot log\ n$$, a więc jest on znacznie wydajniejszy niż sortowanie bąbelkowe, przez wstawianie czy przez selekcję, gdzie złożoność jest kwadratowa. Żeby zrozumieć zasadę działania przyjrzyjmy się najpierw dwóm posortowanym tablicom:

tablica 1: 2 3 7 9 10

tablica 2: 1 3 4 8 11

Zauważ, że możesz liniowo scalić te dwa ciągi liczb i uzyskać jedną posortowaną tablicę:

• ustawmy liczniki tak, aby wskazywały pierwsze elemnety każdej z tablic,
• następnie porównujemy elementy i mniejszy z nich zapisujemy w scalonej tablicy,
• zwiększamy licznik w tej tablicy, z której "zabraliśmy element",
• czynność powtarzamy aż do wyczerpania danych z obu tablic.

A więc najpierw musimy doprowadzić do sytuacji, gdzie będziemy mieli dwie posortowane tablice. Dzielimy nasz zbiór liczb na dwie części, następnie każdą z nich także dzielimy na dwie części, czynność powtarzamy do momentu otrzymania podtablic jednoelementowych (wykonujemy to rekurencyjnie) — podział. Ponieważ zbiór jednoelementowy jest już posortowany możemy przejść do scalania. W ten sposób powstają nam coraz to większe posortowane zbiory, aż w rezultacie otrzymamy oczekiwany efekt - ciąg posortowanych elementów — zwycięztwo

Zalety algorytmu

• łatwy w implementacji
• stabilny (elementy o tych samych wartościach nie zamieniają się ze sobą)
• algorytm sortuje zbiór n-elementowy w czasie proporcjonalnym do liczby $$n \log n$$ bez względu na rodzaj danych wejściowych

 Wady algorytmu

• podczas scalania potrzebny jest dodatkowy obszar pamięci przechowujący kopie podtablic do scalenia

Schemat:

Zadanie

Posortuj zbiór liczb całkowitych algorytmem sortowania przez scalanie.

Wejście

W pierwszym wierszu jedna liczba n określająca ilość liczb do posortowania (nie większa niż milion). W kolejnych n wierszach po jednej liczbie całkowitej należącej do przedziału: [-10⁹...10⁹].

Wyjście

Posortowany zbiór liczb całkowitych wypisany w oddzielnych wierszach.

Przykład

Wejście:

5
4
3
5
7
1

Wyjście:

1
3
4
5
7

#*****************www.algorytm.edu.pl****************
def scal(lista: list, pomocnicza: list, lewy, srodek, prawy):

    # kopiujemy lewą i prawą część tablicy do tablicy pomocniczej
    for i in range(lewy, prawy+1):
        pomocnicza[i] = lista[i]

    i = lewy;
    j = srodek + 1
    # scalenie dwóch podtablic pomocniczych i zapisanie ich
    # we właściwej tablicy
    for k in range(lewy, prawy+1):
        if i <= srodek:
            if j <= prawy:
                if pomocnicza[j] < pomocnicza[i]:
                    lista[k] = pomocnicza[j]
                    j+=1
                else:
                    lista[k] = pomocnicza[i]
                    i+=1
            else:
                lista[k] = pomocnicza[i]
                i+=1
        else:
         
            lista[k] = pomocnicza[j]
            j+=1

def sortowanie_przez_scalanie(lista, pomocnicza, lewy, prawy):
    #gdy mamy jeden element, to jest on już posortowany w ramach tego jednoelementowego zbioru
    if lewy < prawy:
        # znajdujemy środek podtablicy
        srodek = (prawy + lewy) // 2
        # dzielimy tablice na częsć lewą i prawą
        sortowanie_przez_scalanie(lista, pomocnicza, lewy, srodek)
        sortowanie_przez_scalanie(lista, pomocnicza, srodek + 1, prawy)
        # scalamy dwie już posortowane tablice
        scal(lista, pomocnicza, lewy, srodek, prawy)

n = int(input()) # podajemy liczbę elementów do posortowania
lista = []        # w tej liście będziemy przechowywać elementy do posortowania
pomocnicza = n*[0]   # ta lista jest pomocniczą, którą wykorzystamy przy scalaniu
for i in range(n): 
    lista.append(int(input())) # wczytanie danych zapisanych w oddzielnych wierszach
# lista = list(map(int, input().split())) # wczytanie danych zapisanych w jednym wierszu

sortowanie_przez_scalanie(lista, pomocnicza, 0, n - 1)

# wypisanie wyników
for i in range(n):
    print(lista[i])