Sortowanie przez wstawianie

🎯 Po co Ci to?

Weź do ręki rozdawane karty. Nie sortujesz ich bąbelkowo — robisz coś naturalniejszego: każdą nową kartę wsuwasz na właściwe miejsce między te, które już trzymasz posortowane. Gratulacje: znasz sortowanie przez wstawianie od dziecka. Dziś tylko je zapiszesz — i odkryjesz, czemu ten „ręczny" algorytm, na oko bliźniak bąbelkowego, jest od niego w praktyce wyraźnie lepszy: tak dobry, że zawodowe biblioteki sortujące do dziś wołają go do małych i prawie posortowanych danych.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • wykonać i zaprogramować sortowanie przez wstawianie (z przesuwaniem, nie zamianami);
  • wskazać niezmiennik („początek listy zawsze posortowany") i uzasadnić poprawność;
  • porównać koszty z bąbelkowym: najgorszy, najlepszy i „prawie posortowany" przypadek.

🔁 Przypomnij sobie

Z 6.3: niezmiennik i liczenie kosztów; z 6.2 (zadanie 3): binarne szukanie pozycji wstawienia — dziś zobaczysz, gdzie ono pasuje.

📘 Wyjaśnienie

Pomysł. Utrzymuj lewą część listy posortowaną (na początku: sam pierwszy element). Bierz kolejny element i wsuń go we właściwe miejsce lewej części, przesuwając większych sąsiadów o jedno w prawo:

def wstawianie(L):
    for i in range(1, len(L)):        # element L[i] wchodzi do gry
        klucz = L[i]                  # zapamiętaj go — zaraz go nadpiszemy!
        j = i - 1
        while j >= 0 and L[j] > klucz:
            L[j + 1] = L[j]           # przesuń większego w prawo
            j = j - 1
        L[j + 1] = klucz              # wsuń klucz w powstałą lukę

Prześledź w wyobraźni rękę z kartami: klucz to nowa karta trzymana w powietrzu, pętla while to rozsuwanie wachlarza, ostatnia linijka — wsunięcie. Zauważ, że nie ma tu zamian — są przesunięcia (jedno przypisanie zamiast trzech), i to pierwsza przewaga nad bąbelkowym. Warunek j >= 0 and L[j] > klucz czytaj uważnie: kolejność członów ma znaczenie, bo Python sprawdzi L[j] tylko, gdy j >= 0 przeszło — odwróć człony, a lista pierwszy element przywita Cię błędem indeksu (L[-1] w Pythonie to legalnie… ostatni element — cichy horror zamiast głośnego błędu!).

Niezmiennik i poprawność. Po obsłużeniu elementu $i$: pierwsze $i+1$ elementów jest posortowane (to te same elementy co na starcie, tylko uporządkowane — wstawianie niczego nie gubi ani nie dubluje). Po ostatnim obrocie niezmiennik obejmuje całość. Krótko i elegancko — a na maturze takie zdanie to komplet punktów za „uzasadnij poprawność".

Koszt — i tu robi się ciekawie. Najgorszy przypadek (lista odwrócona): każdy klucz wędruje na sam początek — $\frac{n(n-1)}{2}$ porównań i przesunięć, kwadratowo, remis z bąbelkowym. Ale najlepszy (lista posortowana): każdy klucz od razu trafia (jedno porównanie, zero przesunięć) — $n-1$ porównań, liniowo, bez żadnej flagi — to zachowanie jest wbudowane w algorytm. A między skrajnościami działa piękna reguła z zadania 6.3/2: liczba przesunięć = liczba inwersji listy. Lista „prawie posortowana" (kilka świeżych elementów, lekko poprzestawiane sąsiedztwa) ma mało inwersji — i wstawianie śmiga po niej niemal liniowo. Dlatego to właśnie wstawianie sortuje w praktyce: końcówki dużych sortowań, dopisywane na bieżąco rankingi, strumienie prawie uporządkowanych danych.

💭 Pomyśl: W 6.2 (zadanie 3) napisałeś binarne szukanie pozycji wstawienia. Czy podmieniając w dzisiejszym algorytmie liniowe cofanie się na binarne szukanie miejsca, przyspieszysz sortowanie z $n^2$ do $n \log n$?

Sprawdź odpowiedź

Niestety nie — i zrozumienie „czemu nie" jest cenniejsze niż niejedno „tak". Binarne szukanie zmniejsza liczbę porównań do $\log i$ na element (łącznie $n \log n$ — pięknie). Ale samo wsunięcie wciąż wymaga przesunięcia wszystkich większych elementów o jedno pole — a przesunięć jest tyle, ile inwersji: w najgorszym razie $\frac{n(n-1)}{2}$, i żadne sprytne szukanie tego nie zmieni. Wąskim gardłem nie było szukanie, tylko robienie miejsca w tablicy, gdzie wstawienie w środek kosztuje przesunięcie ogona. Chcesz taniego wstawiania w środek? Potrzebujesz innej struktury danych — listy wiązanej. Ta obserwacja to most prosto do działu 9.

🧮 Prześledź

wstawianie([5, 2, 4, 6, 1]) — pokaż listę po obsłużeniu każdego i i policz przesunięcia.

Sprawdź odpowiedź

$i=1$ (klucz 2): 5 w prawo → [2,5,4,6,1], 1 przesunięcie. $i=2$ (klucz 4): 5 w prawo → [2,4,5,6,1], 1. $i=3$ (klucz 6): nic (6 > 5) → bez zmian, 0. $i=4$ (klucz 1): 6,5,4,2 wszystkie w prawo → [1,2,4,5,6], 4. Razem 6 przesunięć — i policz inwersje listy wejściowej: (5,2),(5,4),(5,1),(2,1),(4,1),(6,1) — sześć. Zgadza się co do sztuki; ta równość to najlepszy „test jednostkowy" Twojego śledzenia.

⚠️ Uwaga, pułapka

Linia klucz = L[i] wygląda na zbędną ceremonię — czemu nie pracować wprost na L[i]? Bo pierwsze przesunięcie (L[j+1] = L[j] przy $j = i-1$) nadpisuje pozycję $i$! Bez odłożenia klucza do zmiennej wstawiany element ginie pod przesuwaną falą i lista zaczyna zawierać duplikaty. Uruchom w głowie [3, 1] bez linijki z kluczem — zobaczysz [3, 3]. Klasyka błędów „przecież to samo": kolejność zapisów w tablicy bywa treścią algorytmu.

🌍 Powiązania

Wstawianie ma jeszcze jedną zawodową rolę: sortowanie na żywo. Gdy dane przychodzą strumieniem (wyniki zawodników wpadają po kolei, kolejne pomiary z czujnika — dział 3.7), wstawianie utrzymuje listę posortowaną cały czas, kosztem małej pracy przy każdym przybyszu. Bąbelkowe czy scalanie potrzebują całości z góry; wstawianie jest gościnne. W dziale 9 struktura zwana kopcem zrobi to samo jeszcze sprytniej — ale idea „utrzymuj porządek przyrostowo" rodzi się tutaj.

🛠️ Teraz Ty

Bez komputera: posortuj wstawianiem litery słowa GRUDZIEN (porządek alfabetyczny), notując przesunięcia. Z komputerem: dołóż do wstawianie liczniki porównań i przesunięć; uruchom na tych samych trzech listach, co bąbelkowe w 6.3 (posortowana, odwrócona, losowa) i zestaw wyniki obu algorytmów w tabelce. Który wygrywa gdzie?

📐 Definicje tej lekcji

  • Sortowanie przez wstawianie — utrzymuj posortowany przedrostek; kolejny element wsuwaj przesunięciami na właściwe miejsce.
  • Inwersja — para elementów w złej kolejności; liczba przesunięć wstawiania = liczba inwersji wejścia.

📌 Najważniejsze w pigułce

  • Karty w ręce: klucz w powietrzu, więksi w prawo, wsunięcie w lukę — bez zamian, przesunięciami.
  • Posortowany przedrostek to niezmiennik; poprawność w jednym zdaniu.
  • Najgorzej $n^2$, najlepiej $n$ bez flagi; na prawie posortowanych danych — praktyczny mistrz świata.

🎒 Zadania

  1. Dla listy [2, 3, 4, 5, 1] policz przesunięcia wstawiania — najpierw przewidź przez inwersje, potem prześledź.
Wskazówka i odpowiedź

Inwersje: jedynka stoi za wszystkimi — (2,1),(3,1),(4,1),(5,1) — cztery. Śledzenie: klucze 3, 4, 5 wchodzą bez pracy; klucz 1 przesuwa 5,4,3,2 — cztery przesunięcia ✓. Jedna zabłąkana mała wartość na końcu psuje dokładnie tyle, ile wynosi jej droga do domu — lokalna miara bałaganu w akcji.

  1. Które sortowanie wybierzesz i dlaczego: (a) ranking 30 uczniów po dopisaniu 2 nowych wyników, (b) odwrócony chronologicznie dziennik 10 000 wpisów, (c) 20 losowych liczb w zadaniu domowym?
Wskazówka i odpowiedź

(a) wstawianie — dwa świeże elementy to garść inwersji, koszt niemal liniowy. (b) pułapka: „odwrócony" to najgorszy przypadek obu poznanych sortowań ($\frac{n(n-1)}{2} \approx 50$ mln operacji — może już nieprzyjemne); tu warto poczekać na 6.6/6.7 (albo… odwrócić listę wprost — odwracanie to nie sortowanie i kosztuje $n/2$ zamian!). (c) obojętne — przy $n=20$ każdy algorytm zdąży przed naciśnięciem Enter; wybierz najprostszy do bezbłędnego napisania. Dobór algorytmu zaczyna się od danych, nie od rankingu algorytmów.

  1. Wstawianie jest stabilne: elementy równe zachowują wyjściową kolejność względem siebie. Wskaż w kodzie miejsce, które o tym decyduje — i podaj przykład z życia, gdzie stabilność ma znaczenie.
Wskazówka i odpowiedź

Warunek L[j] > klucz (ostra nierówność!): równy element nie jest przesuwany, więc nowy staje ZA starym równym sobie. Z >= kolejność równych by się odwracała — niestabilność. Znaczenie: sortujesz listę uczniów po ocenie, a była posortowana alfabetycznie — przy stabilnym sortowaniu uczniowie z tą samą oceną pozostają w porządku alfabetycznym „za darmo". Sortowanie wielokryterialne (najpierw po nazwisku, potem stabilnie po ocenie) to standardowa sztuczka — zapamiętaj ją do działu 11, gdzie posortujesz tak arkusz.

🔍 Sprawdź, czy umiesz

  • Zapisać wstawianie z pamięci — z kluczem, przesunięciami i poprawnym warunkiem pętli.
  • Przewidzieć koszt przez liczbę inwersji i sprawdzić śledzeniem.
  • Uzasadnić, czemu biblioteki wołają wstawianie do małych i prawie posortowanych danych.

Ucz się tej jednostki z asystentem