Sortowanie przez scalanie i sortowanie szybkie

Proste sortowania z zakresu podstawowego wykonują w najgorszym przypadku około n²/2 porównań. Szybsze sortowania korzystają z metody dziel i zwyciężaj: dzielą tablicę na części, sortują je rekurencyjnie i składają wynik. Tak działają sortowanie przez scalanie i sortowanie szybkie. Ta sama metoda pozwala znaleźć jednocześnie minimum i maksimum w mniejszej liczbie porównań.

Każdy przykład przejdziesz krok po kroku w kursie Algorytmy: zakres rozszerzony: w przeglądarce, bez instalowania niczego i bez konta. Stos wywołań pokazuje, który fragment tablicy sortuje właśnie bieżące wywołanie.

Przejdź sortowanie przez scalanie krok po kroku

Minimum i maksimum metodą par

Zamiast porównywać każdy element osobno z minimum i z maksimum, elementy bierze się parami: mniejszy z pary może być tylko nowym minimum, a większy tylko nowym maksimum.

def min_max(values):
    comparisons = 0
    if len(values) % 2 == 1:
        low = high = values[0]
        start = 1
    else:
        comparisons += 1
        low, high = sorted(values[:2])
        start = 2
    for i in range(start, len(values), 2):
        a, b = values[i], values[i + 1]
        comparisons += 3
        if a > b:
            a, b = b, a
        if a < low:
            low = a
        if b > high:
            high = b
    return low, high, comparisons


print(min_max([3, 8, 1, 9, 4, 7]))
print(min_max(list(range(100)))[2])

(1, 9, 7)
148

Dla 100 liczb to 148 porównań zamiast 198 przy osobnym szukaniu minimum i maksimum.

Sortowanie przez scalanie

Dwie posortowane listy łatwo scalić w jedną: wystarczy porównywać ich pierwsze elementy i przenosić mniejszy. Sortowanie przez scalanie dzieli tablicę na połowy, sortuje każdą rekurencyjnie i scala wyniki:

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
    return result + left[i:] + right[j:]


def merge_sort(values):
    if len(values) <= 1:
        return values
    middle = len(values) // 2
    return merge(merge_sort(values[:middle]), merge_sort(values[middle:]))


print(merge_sort([5, 2, 9, 1, 5, 6]))

[1, 2, 5, 5, 6, 9]

Tablica dzieli się na połowy log₂ n razy, a na każdym poziomie scalanie przegląda wszystkie n elementów: razem O(n log n) porównań w każdym przypadku. Warunek <= zostawia równe elementy w kolejności początkowej, więc sortowanie jest stabilne.

Sortowanie szybkie

Sortowanie szybkie wybiera element osiowy (tu ostatni element fragmentu), przestawia mniejsze elementy przed niego, a większe za niego, i sortuje rekurencyjnie obie części. Element osiowy stoi już na swoim miejscu.

def partition(values, low, high):
    pivot = values[high]
    i = low - 1
    for j in range(low, high):
        if values[j] < pivot:
            i += 1
            values[i], values[j] = values[j], values[i]
    values[i + 1], values[high] = values[high], values[i + 1]
    return i + 1


def quick_sort(values, low, high):
    if low < high:
        q = partition(values, low, high)
        quick_sort(values, low, q - 1)
        quick_sort(values, q + 1, high)


numbers = [5, 2, 9, 1, 5, 6]
quick_sort(numbers, 0, len(numbers) - 1)
print(numbers)

[1, 2, 5, 5, 6, 9]

Zwykle podział jest w miarę równy i sortowanie wykonuje około n log₂ n porównań. Na tablicy już posortowanej ostatni element jest zawsze największy, podział odcina jeden element i liczba porównań rośnie do n(n-1)/2.

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Minimum i maksimum metodą par

Specyfikacja. Dane: tablica T[1..n], n ≥ 1. Wynik: najmniejszy (mn) i największy (mx) element tablicy.

Lista kroków:

1. Wczytaj n i tablicę T[1..n].
2. Jeśli n jest nieparzyste, ustaw mn = mx = T[1] i i = 2. W przeciwnym razie porównaj T[1] z T[2]: mniejszy to mn, większy to mx, i ustaw i = 3.
3. Jeśli i > n - 1, przejdź do kroku 6.
4. Porównaj parę T[i] i T[i + 1]: mniejszy z nich (m) porównaj z mn, a większy (w) porównaj z mx i popraw mn albo mx.
5. Zwiększ i o 2 i wróć do kroku 3.
6. Wypisz mn i mx.

Pseudokod:

wczytaj n, T
jeżeli n mod 2 = 1 to
  mn ← T[1]
  mx ← T[1]
  i ← 2
w przeciwnym razie
  jeżeli T[1] < T[2] to
    mn ← T[1]
    mx ← T[2]
  w przeciwnym razie
    mn ← T[2]
    mx ← T[1]
  i ← 3
dopóki i < n wykonuj
  jeżeli T[i] < T[i + 1] to
    m ← T[i]
    w ← T[i + 1]
  w przeciwnym razie
    m ← T[i + 1]
    w ← T[i]
  jeżeli m < mn to
    mn ← m
  jeżeli w > mx to
    mx ← w
  i ← i + 2
wypisz mn, mx

Schemat blokowy:

Drzewo decyzyjne minimum i maksimum trzech liczb. Każdy węzeł to porównanie dwóch elementów (a, b, c w kolejności w tablicy), liść to para: najmniejszy i największy element. Pierwszy element od razu jest kandydatem na oba wyniki, a para b, c wymaga trzech porównań zamiast czterech. Algorytm wykonuje 3 porównania. Węzeł z jedną gałęzią to porównanie, którego wynik wynika już z wcześniejszych porównań: algorytm i tak je wykonuje.

Sortowanie przez scalanie

Specyfikacja. Dane: tablica T[1..n]. Wynik: tablica T posortowana niemalejąco.

Lista kroków:

1. Wczytaj n i tablicę T[1..n], wykonaj sortuj(T, 1, n) i wypisz T.
2. sortuj(T, l, p): jeśli l ≥ p, fragment ma najwyżej jeden element i jest posortowany.
3. W przeciwnym razie podziel fragment w połowie s = (l + p) div 2, posortuj rekurencyjnie T[l..s] i T[s + 1..p].
4. scal(T, l, s, p): dopóki w obu połówkach zostały elementy, przepisuj do tablicy pomocniczej P mniejszy z pierwszych elementów połówek, potem resztę tej połówki, która się nie skończyła.
5. Przepisz P z powrotem na miejsce T[l..p].

Pseudokod:

funkcja scal(T, l, s, p)
  i ← l
  j ← s + 1
  k ← 1
  dopóki i ≤ s lub j ≤ p wykonuj
    jeżeli j > p lub (i ≤ s i T[i] ≤ T[j]) to
      P[k] ← T[i]
      i ← i + 1
    w przeciwnym razie
      P[k] ← T[j]
      j ← j + 1
    k ← k + 1
  dla k = 1, 2, ..., p - l + 1 wykonuj
    T[l + k - 1] ← P[k]
funkcja sortuj(T, l, p)
  jeżeli l < p to
    s ← (l + p) div 2
    sortuj(T, l, s)
    sortuj(T, s + 1, p)
    scal(T, l, s, p)
wczytaj n, T
sortuj(T, 1, n)
wypisz T

Schemat blokowy:

Drzewo decyzyjne sortowania trzech liczb przez scalanie. Każdy węzeł to porównanie dwóch elementów (a, b, c to elementy tablicy w kolejności początkowej), liść to wynik sortowania. Drzewo policzone z przebiegów algorytmu dla wszystkich 6 ułożeń trzech różnych liczb. Algorytm wykonuje od 2 do 3 porównań.

Sortowanie szybkie

Specyfikacja. Dane: tablica T[1..n]. Wynik: tablica T posortowana niemalejąco.

Lista kroków:

1. Wczytaj n i tablicę T[1..n], wykonaj sortuj(T, 1, n) i wypisz T.
2. sortuj(T, l, p): jeśli l ≥ p, zakończ.
3. Podziel fragment funkcją podziel(T, l, p): element osiowy x = T[p], elementy mniejsze od x przenieś na początek fragmentu, a x postaw zaraz za nimi na pozycji q.
4. Posortuj rekurencyjnie T[l..q - 1] i T[q + 1..p]. Element T[q] stoi już na swoim miejscu.

Pseudokod:

funkcja podziel(T, l, p)
  x ← T[p]
  i ← l - 1
  dla j = l, l + 1, ..., p - 1 wykonuj
    jeżeli T[j] < x to
      i ← i + 1
      zamień T[i] z T[j]
  zamień T[i + 1] z T[p]
  zwróć i + 1
funkcja sortuj(T, l, p)
  jeżeli l < p to
    q ← podziel(T, l, p)
    sortuj(T, l, q - 1)
    sortuj(T, q + 1, p)
wczytaj n, T
sortuj(T, 1, n)
wypisz T

Schemat blokowy:

Drzewo decyzyjne sortowania szybkiego trzech liczb. Każdy węzeł to porównanie dwóch elementów (a, b, c to elementy tablicy w kolejności początkowej), liść to wynik sortowania. Drzewo policzone z przebiegów algorytmu dla wszystkich 6 ułożeń trzech różnych liczb. Algorytm wykonuje od 2 do 3 porównań.

Najczęstsze błędy

• Zgubiona reszta po scaleniu. Pętla scalania kończy się, gdy skończy się jedna z list. Resztę drugiej trzeba dopisać (left[i:] + right[j:]).
• Złe granice fragmentów. W sortowaniu szybkim rekurencja dostaje fragmenty low..q - 1 i q + 1..high. Gdy element osiowy trafi do któregoś z nich, rekurencja może się nie skończyć.
• Nieparzysta liczba elementów w metodzie par. Jeden element zostaje bez pary: najlepiej od razu przyjąć go za minimum i maksimum.
• Sortowanie kopii zamiast tablicy. merge_sort zwraca nową listę, a quick_sort zmienia listę w miejscu. Wywołanie merge_sort(numbers) bez przypisania wyniku nic nie zmienia.

Ćwicz w przeglądarce

W kursie Algorytmy: zakres rozszerzony na start polecam:

• porównywanie parami,
• scalanie dwóch posortowanych list,
• sortowanie szybkie,
• liczba porównań w sortowaniu przez scalanie.

Przycisk Algorytm przy tych lekcjach pokazuje listę kroków, pseudokod, schematy blokowe i drzewa decyzyjne. Proste sortowania z zakresu podstawowego: przez wybieranie, bąbelkowe i przez wstawianie.

Dla nauczycieli

Drzewa decyzyjne dla trzech liczb pozwalają porównać sortowania bez wzorów: uczniowie liczą ścieżki i liście, a krokowanie pokazuje, które elementy są porównywane. W BitWizards przydzielasz kurs klasie i widzisz przebieg pisania kodu każdego ucznia. Platforma jest darmowa dla szkół - jak zacząć.