Rekurencyjnie dzieli tablicę na połowy i scala posortowane części. Złożoność O(n log n).
Sortowanie przez scalanie układa liczby po kolei, dzieląc problem na mniejsze. Najpierw tniesz tablicę na pół, każdą połowę znów na pół, i tak dalej – aż zostaną same pojedyncze liczby. Pojedyncza liczba jest już „ułożona" sama w sobie.
Potem sklejasz je z powrotem. Bierzesz dwa gotowe, ułożone kawałki i łączysz je w jeden większy, też ułożony. Patrzysz na pierwszą liczbę z lewego kawałka i pierwszą z prawego, wybierasz mniejszą i dopisujesz ją do wyniku. Powtarzasz, aż przepiszesz wszystko.
Zawsze tak samo szybko. Ten sposób działa tyle samo czasu niezależnie od tego, czy liczby były wymieszane, czy prawie ułożone. Cena za to jest taka, że potrzebuje dodatkowego miejsca – drugiej tablicy na sklejane kawałki.
Na maturze: to sztandarowy przykład metody „dziel i zwyciężaj" – dużego zadania rozbitego na mniejsze takie same.
Podział – dzielimy na połowy, aż zostaną pojedyncze elementy:
Scalanie – łączymy posortowane fragmenty z powrotem w większe:
Prześledź krok po kroku, jak algorytm porządkuje tablicę. Porównywane elementy są podświetlone, a te, które trafiły na swoje docelowe miejsce, zmieniają kolor na zielony.
Naciśnij „Krok", aby wykonać jedną operację, albo „Auto", aby uruchomić całą animację.
funkcja scal(L, P): wynik ← pusta lista i ← 0 j ← 0 // przechodzimy obie tablice jednocześnie dopóki i < długość(L) oraz j < długość(P): jeżeli L[i] ≤ P[j]: dodaj L[i] do wynik i ← i + 1 w przeciwnym razie: dodaj P[j] do wynik j ← j + 1 // dopisujemy pozostałe elementy dopóki i < długość(L): dodaj L[i] do wynik i ← i + 1 dopóki j < długość(P): dodaj P[j] do wynik j ← j + 1 zwróć wynik funkcja sortuj_przez_scalanie(T): jeżeli długość(T) ≤ 1: zwróć T srodek ← długość(T) div 2 L ← sortuj_przez_scalanie(T[0..srodek - 1]) P ← sortuj_przez_scalanie(T[srodek..koniec]) zwróć scal(L, P)
def scal(lewa, prawa):
wynik = []
i = j = 0
while i < len(lewa) and j < len(prawa):
if lewa[i] <= prawa[j]:
wynik.append(lewa[i])
i += 1
else:
wynik.append(prawa[j])
j += 1
# dopisujemy pozostałe elementy z dłuższej tablicy
wynik.extend(lewa[i:])
wynik.extend(prawa[j:])
return wynik
def sortowanie_przez_scalanie(tablica):
if len(tablica) <= 1:
return tablica
srodek = len(tablica) // 2
lewa = sortowanie_przez_scalanie(tablica[:srodek])
prawa = sortowanie_przez_scalanie(tablica[srodek:])
return scal(lewa, prawa)
# Przykład użycia
dane = [64, 25, 12, 22, 11, 90, 3]
print(sortowanie_przez_scalanie(dane))
# Wynik: [3, 11, 12, 22, 25, 64, 90]#include <vector>
#include <iostream>
using namespace std;
// scala dwie posortowane części tablicy t: [lewy..srodek] oraz [srodek+1..prawy]
void scal(vector<int>& t, int lewy, int srodek, int prawy) {
vector<int> pom;
int i = lewy; // wskaźnik lewej części
int j = srodek + 1; // wskaźnik prawej części
// przechodzimy obie części jednocześnie, wybierając mniejszy element
while (i <= srodek && j <= prawy) {
if (t[i] <= t[j]) pom.push_back(t[i++]);
else pom.push_back(t[j++]);
}
// dopisujemy pozostałe elementy
while (i <= srodek) pom.push_back(t[i++]);
while (j <= prawy) pom.push_back(t[j++]);
// przepisujemy scalony wynik z powrotem do tablicy
for (int k = 0; k < (int)pom.size(); k++)
t[lewy + k] = pom[k];
}
// rekurencyjnie dzieli zakres na pół i scala posortowane połowy
void sortowanie_przez_scalanie(vector<int>& t, int lewy, int prawy) {
if (lewy >= prawy) return; // fragment o długości 0 lub 1 jest już posortowany
int srodek = lewy + (prawy - lewy) / 2;
sortowanie_przez_scalanie(t, lewy, srodek);
sortowanie_przez_scalanie(t, srodek + 1, prawy);
scal(t, lewy, srodek, prawy);
}
int main() {
vector<int> dane = {64, 25, 12, 22, 11, 90, 3};
sortowanie_przez_scalanie(dane, 0, dane.size() - 1);
for (int x : dane) cout << x << " ";
// Wynik: 3 11 12 22 25 64 90
}Nie – w fazie scalania powstaje dodatkowa tablica, do której trafiają posortowane elementy z obu fragmentów, a dopiero potem wynik wraca do oryginalnej tablicy. Stąd złożoność pamięciowa O(n) (patrz sekcja „Złożoność").
Rekurencję warto przerywać wcześniej: dla bardzo krótkich fragmentów sortowanie przez wstawianie wykonuje mniej operacji niż dalsze dzielenie i scalanie. To dokładnie ta sama sztuczka, na której opiera się Timsort.
Sortowanie przez scalanie radzi sobie równie dobrze z każdym zestawem danych – dużym, małym, dowolnie rozłożonym. Sortowanie szybkie bywa za to szybsze w praktyce na małych tablicach, głównie dzięki mniejszym stałym i lepszemu wykorzystaniu pamięci podręcznej procesora.
Nie – ma dokładnie taką samą złożoność w najlepszym, średnim i najgorszym przypadku, niezależnie od tego, jak ułożone są dane wejściowe. To odróżnia je od sortowania przez wstawianie, które na prawie posortowanych danych działa niemal liniowo.
Złożoność O(n log n) jest gwarantowana zawsze, ale sama liczba porównań w fazie scalania bywa różna. Jest największa, gdy elementy obu scalanych fragmentów przeplatają się na zmianę w finalnej kolejności (np. scalanie [1, 3] i [2, 4]) – wtedy trzeba porównać niemal każdą parę, zanim wybierze się mniejszy element.
Policz wartości dla sortowania przez scalanie i wpisz wynik, potem kliknij Sprawdź.
Liczba poziomów podziału dla tablicy o 8 elementach to , a dla 4 elementów to . Scalając dwie posortowane połówki o długościach 4 i 4 wykonasz co najwyżej porównań.
Uzupełnij tabelę (liczba poziomów podziału to log₂ z liczby elementów):
| Liczba elementów | Poziomy podziału |
|---|---|
| 2 | |
| 16 | |
| 32 |
Sortowanie przez scalanie jest stabilne, więc odpowiedz . Jego złożoność pamięciowa to .
O(n log n)O(n log n)O(n)Czas O(n log n) – zawsze. Dzielenie tworzy log n poziomów rekurencji (za każdym razem połowa), a na każdym poziomie scalanie przegląda wszystkie n elementów. Daje to log n poziomów × O(n) pracy = O(n log n). Co ważne, ten rząd jest gwarantowany niezależnie od danych – nie ma złego przypadku, jak w sortowaniu szybkim.
Pamięć O(n). Przy scalaniu tworzymy tablice pomocnicze na wyniki – to koszt O(n). Rekurencja odkłada dodatkowo po jednej ramce na każdy poziom podziału, czyli O(log n) na stosie. Ponieważ w Big-O liczy się składnik dominujący, a n rośnie szybciej niż log n, całość zapisujemy jako O(n). Ta dodatkowa pamięć to główna wada w porównaniu z algorytmami sortującymi w miejscu.
Do tego hasła nie mamy jeszcze przypisanych pojedynczych zadań. Cały spis zadań maturalnych z tego działu jest tutaj:
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: