Sortowanie przez wstawianie

1. Idea algorytmu

Sortowanie przez wstawianie (insertion sort) działa podobnie jak sortowanie kart w ręce:

  1. Zacznij od drugiego elementu
  2. Wstaw go we właściwe miejsce w już posortowanej części
  3. Powtarzaj dla kolejnych elementów

Analogia - sortowanie kart:

Masz karty: [5, 2, 4, 6, 1, 3]

Krok 1: [5] | 2, 4, 6, 1, 3
        ↑ już posortowane

Krok 2: [5] | 2, 4, 6, 1, 3
        Wstaw 2 → [2, 5] | 4, 6, 1, 3

Krok 3: [2, 5] | 4, 6, 1, 3
        Wstaw 4 → [2, 4, 5] | 6, 1, 3

Krok 4: [2, 4, 5] | 6, 1, 3
        Wstaw 6 → [2, 4, 5, 6] | 1, 3

Krok 5: [2, 4, 5, 6] | 1, 3
        Wstaw 1 → [1, 2, 4, 5, 6] | 3

Krok 6: [1, 2, 4, 5, 6] | 3
        Wstaw 3 → [1, 2, 3, 4, 5, 6]

2. Implementacja podstawowa

Wizualizacja krok po kroku:

[64, 25, 12, 22, 11]
 ↑ już posortowane

[64, 25, 12, 22, 11]  key=25
    ↓
[25, 64, 12, 22, 11]  ← 25 wstawione

[25, 64, 12, 22, 11]  key=12
        ↓
[12, 25, 64, 22, 11]  ← 12 wstawione

[12, 25, 64, 22, 11]  key=22
            ↓
[12, 22, 25, 64, 11]  ← 22 wstawione

[12, 22, 25, 64, 11]  key=11
                ↓
[11, 12, 22, 25, 64]  ← 11 wstawione (KONIEC!)

3. Implementacja z wizualizacją

Wynik:

Start: [64, 25, 12, 22, 11]

Iteracja 1: Wstawianie 25
  Przed: [64, 25, 12, 22, 11]
  Przesunięć: 1
  Po:    [25, 64, 12, 22, 11]

Iteracja 2: Wstawianie 12
  Przed: [25, 64, 12, 22, 11]
  Przesunięć: 2
  Po:    [12, 25, 64, 22, 11]

Iteracja 3: Wstawianie 22
  Przed: [12, 25, 64, 22, 11]
  Przesunięć: 1
  Po:    [12, 22, 25, 64, 11]

Iteracja 4: Wstawianie 11
  Przed: [12, 22, 25, 64, 11]
  Przesunięć: 4
  Po:    [11, 12, 22, 25, 64]

Koniec: [11, 12, 22, 25, 64]

4. Złożoność czasowa

Najgorszy przypadek: O(n²)

Lista w odwrotnej kolejności:

Liczba porównań:

Iteracja 1: 1 porównanie (25 vs 64)
Iteracja 2: 2 porównania (12 vs 64, 12 vs 25)
Iteracja 3: 3 porównania
Iteracja 4: 4 porównania
...
Razem: 1 + 2 + 3 + ... + (n-1) = n(n-1)/2 = O(n²)

Najlepszy przypadek: O(n) ← WAŻNE!

Lista już posortowana:

Każdy element wymaga tylko 1 porównania → O(n) całkowicie!

Średni przypadek: O(n²)

Losowe dane - średnio połowa przesunięć.

5. Złożoność pamięciowa: O(1)

Insertion sort jest in-place!

6. Stabilność: TAK ✅

Insertion sort jest stabilny – zachowuje kolejność równych elementów.

Przykład:

Dlaczego? Warunek arr[j] > key (a nie >=) zachowuje stabilność.

7. Optymalizacja: Binary Insertion Sort

Zamiast liniowego szukania miejsca – użyj wyszukiwania binarnego!

Uwaga: Zmniejsza porównania do O(n log n), ale przesunięcia nadal O(n²)!

Wniosek: W praktyce niewielka poprawa.

8. Insertion sort dla małych tablic

Dlaczego jest używany w praktyce?

Wiele zaawansowanych algorytmów (Timsort, Introsort) używa insertion sort dla małych fragmentów (n < 10-20).

Zalety dla małych danych: - Niski overhead (brak rekurencji) - Cache-friendly (sekwencyjny dostęp) - Prosty kod (mniej błędów)

9. Porównanie: Insertion vs Bubble vs Selection

Aspekt Insertion Bubble Selection
Najlepszy przypadek O(n) ✅ O(n) O(n²) ❌
Najgorszy przypadek O(n²) O(n²) O(n²)
Stabilny ✅ TAK ✅ TAK ❌ NIE
Adaptywny ✅ TAK ✅ TAK (z opt) ❌ NIE
Liczba zamian O(n²) O(n²) O(n) ✅

Insertion vs Bubble: - Insertion lepszy dla prawie posortowanych (mniej operacji) - Insertion szybszy w praktyce (mniej zamian)

Insertion vs Selection: - Insertion adaptywny (Selection zawsze O(n²)) - Insertion lepszy dla prawie posortowanych

10. Benchmark

Przykładowe wyniki:

--- 100 elementów ---
Losowe:           0.0021s
Prawie posortowane: 0.0002s (×10.5 szybciej!)

--- 500 elementów ---
Losowe:           0.0512s
Prawie posortowane: 0.0008s (×64.0 szybciej!)

--- 1000 elementów ---
Losowe:           0.2048s
Prawie posortowane: 0.0015s (×136.5 szybciej!)

Wniosek: Dla prawie posortowanych – BARDZO szybki!

11. Wariant: Sortowanie malejąco

12. Zastosowanie praktyczne: Sortowanie częściowo posortowanych

Złożoność: O(n) dla prawie posortowanych!

13. Liczenie inwersji

Inwersja = para elementów (i, j) gdzie i < j ale arr[i] > arr[j].

Zastosowanie: Mierzenie "odwrotności" listy.

14. Podsumowanie

Insertion Sort:

  • Złożoność czasowa:
  • Najlepszy: O(n) ← Dla posortowanych!
  • Średni: O(n²)
  • Najgorszy: O(n²)
  • Złożoność pamięciowa: O(1) in-place
  • Stabilny: TAK ✅
  • Adaptywny: TAK ✅ (szybszy dla prawie posortowanych)

Zalety: - Bardzo szybki dla małych/prawie posortowanych danych - Prosty w implementacji - In-place (O(1) pamięci) - Stabilny - Adaptywny (O(n) dla posortowanych)

Wady: - O(n²) dla losowych danych - Wolny dla dużych danych - Dużo przesunięć elementów

vs Bubble Sort: - Insertion lepszy w praktyce (mniej operacji) - Insertion szybszy dla prawie posortowanych

vs Selection Sort: - Insertion adaptywny (Selection zawsze O(n²)) - Insertion lepszy dla prawie posortowanych - Selection mniej zamian O(n) (Insertion O(n²))

Kiedy używać:

✅ Małe dane (n < 50) ✅ Prawie posortowane dane (bardzo szybkie!) ✅ Online sorting (sortowanie w czasie rzeczywistym) ✅ Jako część Timsort dla małych fragmentów

❌ Duże losowe dane – użyj quick/merge sort!

Przykłady zastosowań:

  1. Timsort (Python) – używa insertion sort dla run < 64
  2. Introsort (C++) – używa insertion sort dla małych partycji
  3. Online algorithms – sortowanie w czasie rzeczywistym
  4. Prawie posortowane dane – najbardziej efektywny

Co dalej warto poznać:

  • Merge Sort (gwarantowane O(n log n))
  • Quick Sort (średnio najszybszy)
  • Timsort (hybrydowy algorytm Pythona)
  • Shell Sort (ulepszona wersja insertion sort)
Wróć do spisu lekcji