Podcast o Sortowanie przez wstawianie (insertion sort)

Kapitoly

Układanie kart w ręku

Podział na dwie części

Przykład krok po kroku

Złożoność i wydajność

Typowe błędy i stabilność algorytmu

Podsumowanie: Kiedy używać?

Najgorszy i najlepszy przypadek

Podsumowanie i pożegnanie

Přepis

Alicja: Pomyśl o ostatniej grze w karty, w jaką grałeś. Rozdano ci karty i co robisz? Zapewne bierzesz je do ręki i zaczynasz układać — dwójki tu, trójki tam, asy na końcu. Bierzesz jedną kartę, znajdujesz dla niej miejsce i wsuwasz, przesuwając resztę. Okazuje się, że ten naturalny, ludzki odruch to jeden z fundamentalnych algorytmów w informatyce.

Jakub: Dokładnie tak. I nawet jego nazwa idealnie to oddaje, bo mówimy o sortowaniu przez wstawianie. To, co robisz z kartami bez zastanowienia, komputery robią według precyzyjnych instrukcji. Właśnie na tym to polega.

Alicja: Słuchacie Studyfi Podcast. Tutaj skomplikowane tematy z matury i studiów tłumaczymy tak, żebyście je naprawdę zrozumieli. Kuba, czyli nasz ekspert, rozłoży dzisiaj na czynniki pierwsze właśnie sortowanie przez wstawianie.

Jakub: Zgadza się. Zaczniemy od tego, że algorytm dzieli naszą listę — na przykład tablicę liczb — na dwie części. Wyobraź sobie linię na piasku. Po jednej stronie masz już posortowane elementy, a po drugiej bałagan, który musimy uporządkować.

Alicja: Czyli na początku ta posortowana część jest... pusta?

Jakub: Prawie. Na starcie zakładamy, że pierwszy element sam w sobie tworzy posortowaną część. No bo jedna liczba zawsze jest posortowana, prawda? A cała reszta tablicy to część nieposortowana.

Alicja: Okej, to ma sens. I co dalej? Bierzemy pierwszą liczbę z tego bałaganu?

Jakub: Właśnie tak! Bierzemy pierwszy element z nieposortowanej części — nazwijmy go „kluczem” — i szukamy dla niego odpowiedniego miejsca w tej już posortowanej części. Wstawiamy go tam, gdzie pasuje.

Alicja: A co jeśli po drodze są większe liczby? Trzeba je... przesunąć?

Jakub: Dokładnie. Przesuwasz wszystkie większe elementy o jedno miejsce w prawo, żeby zrobić miejsce dla naszego klucza. Powtarzasz ten proces — bierzesz kolejny klucz, wstawiasz, przesuwasz — aż w nieposortowanej części nie zostanie już nic.

Alicja: Dobra, teoria brzmi prosto. Ale moglibyśmy prześledzić to na konkretnym przykładzie? Powiedzmy, że mamy tablicę liczb: 5, 2, 4, 6, 1, 3.

Jakub: Świetny przykład. Zaczynamy. Tablica to . Posortowana część to na razie tylko . Reszta to bałagan.

Alicja: Krok pierwszy: bierzemy dwójkę.

Jakub: Tak. Naszym kluczem jest 2. Patrzymy na posortowaną część, czyli na 5. Czy 5 jest większe od 2? Jest. Więc przesuwamy 5 w prawo i wstawiamy 2 na jej miejsce. Tablica wygląda teraz tak: . Posortowana część urosła do .

Alicja: Proste. Następna w kolejce jest czwórka. Co z nią?

Jakub: Kluczem jest 4. Idziemy od prawej strony posortowanej części. Porównujemy 4 z 5. Piątka jest większa, więc przesuwamy ją w prawo. Potem porównujemy 4 z 2. Dwójka jest mniejsza, więc znaleźliśmy miejsce! Wstawiamy 4 za dwójką. Mamy .

Alicja: Widzę schemat! Z szóstką będzie łatwo. Jest większa od piątki, więc zostaje na swoim miejscu, prawda?

Jakub: Dokładnie! Porównujemy 6 z 5, jest większa, więc pętla od razu się kończy. Nic nie przesuwamy. To ważna cecha tego algorytmu. Tablica bez zmian, a posortowana część to teraz .

Alicja: Ale teraz czeka nas najgorsze... jedynka. Trzeba będzie wszystko poprzesuwać.

Jakub: Niestety tak. Klucz to 1. Porównujemy z 6, 5, 4 i 2. Wszystkie są większe, więc wszystkie po kolei przesuwamy o jedno miejsce w prawo. Jedynka ląduje na samym początku. Tablica: .

Alicja: I ostatnia jest trójka. Szybko zgaduję: wyląduje między dwójką a czwórką.

Jakub: Strzał w dziesiątkę. Przesuwamy 6, 5 i 4, aż trafimy na 2, która jest mniejsza. Wstawiamy 3 na odpowiednie miejsce. Wynik końcowy: . Posortowane!

Alicja: Okej, to było całkiem obrazowe. Ale czuję, że to przesuwanie... może być kosztowne. Jak to wygląda pod kątem wydajności? Kiedy ten algorytm jest szybki, a kiedy wolny jak żółw?

Jakub: Bardzo dobre pytanie. Mówimy tu o złożoności obliczeniowej. W najgorszym przypadku, czyli gdybyśmy mieli tablicę posortowaną od największej do najmniejszej liczby, złożoność wynosi O(n²), czyli „O od n kwadrat”.

Alicja: Co to znaczy w praktyce? Że dla 10 liczb to sto operacji, a dla tysiąca już milion?

Jakub: Mniej więcej tak. Liczba operacji rośnie kwadratowo w stosunku do liczby elementów. To bardzo dużo i dlatego dla ogromnych, losowych zbiorów danych ten algorytm jest po prostu niepraktyczny.

Alicja: A ten najlepszy przypadek, o którym wspomniałeś przy szóstce?

Jakub: Najlepszy przypadek to dane już posortowane. Wtedy algorytm tylko przechodzi przez listę i sprawdza, czy wszystko jest na miejscu. To złożoność O(n) — liniowa. Niezwykle szybka! Dlatego insertion sort jest genialny do sortowania list, które są *prawie* posortowane.

Alicja: A co z pamięcią? Czy potrzebujemy drugiej, pomocniczej tablicy na te wszystkie przesunięcia?

Jakub: I tu jest kolejna zaleta: nie. Sortowanie przez wstawianie działa „w miejscu” (in-place). Potrzebuje tylko stałej ilości dodatkowej pamięci, na przykład na przechowanie naszego „klucza”. Złożoność pamięciowa to O(1). To bardzo oszczędne.

Alicja: Skoro jest taki prosty, to pewnie łatwo go napisać. Ale czy są jakieś pułapki, w które studenci często wpadają?

Jakub: O tak, są dwie klasyczne pułapki. Pierwsza to warunek w pętli, która przesuwa elementy. Trzeba pamiętać, żeby sprawdzać nie tylko, czy element jest większy od klucza, ale też czy nie wyszliśmy poza tablicę! Czyli warunek j >= 0 jest absolutnie kluczowy.

Alicja: Błąd o jeden indeks i cały program się wysypuje. Znam to.

Jakub: Druga pułapka to miejsce wstawienia klucza. Po tym, jak pętla przesuwająca się skończy, wstawiamy klucz na pozycję j+1, a nie j. To dlatego, że pętla zatrzymuje się na pierwszym elemencie, który jest mniejszy lub równy, albo gdy j spadnie do -1. Miejsce jest zawsze o jeden dalej.

Alicja: A co to znaczy, że algorytm jest „stabilny”? Często słyszę to pojęcie.

Jakub: Stabilność to bardzo ważna cecha. Wyobraź sobie, że sortujesz listę studentów po ocenach, ale masz też ich imiona. Jeśli dwóch studentów ma tę samą ocenę, stabilny algorytm zagwarantuje, że ich wzajemna kolejność się nie zmieni. Jeśli Jan był przed Anną, a oboje mają piątkę, to po sortowaniu Jan nadal będzie przed Anną.

Alicja: I sortowanie przez wstawianie jest stabilne?

Jakub: Tak, jest. Dzieje się tak, ponieważ przesuwamy elementy tylko wtedy, gdy są *ściśle większe* od naszego klucza. Gdy algorytm natrafi na element o tej samej wartości, zatrzymuje się i wstawia klucz *za* nim. To zachowuje pierwotną kolejność.

Alicja: Dobrze, podsumujmy. Mamy algorytm, który jest prosty, intuicyjny jak układanie kart, super szybki dla małych lub prawie posortowanych list i nie zjada pamięci. Ale jest tragicznie wolny dla dużych, pomieszanych zbiorów.

Jakub: Dokładnie. Jest idealny do małych zadań. Co ciekawe, niektóre bardzo zaawansowane algorytmy, jak Introsort, używają sortowania przez wstawianie dla małych podproblemów, bo dla kilkunastu czy kilkudziesięciu elementów jest ono szybsze niż te „wielkie” algorytmy jak Quicksort.

Alicja: Czyli to takie narzędzie specjalistyczne? Nie do wszystkiego, ale w swojej niszy niezastąpione.

Jakub: Trafiłaś w sedno. To fundament, który każdy programista powinien znać. I dowód na to, że czasami najprostsze rozwiązania są zaskakująco skuteczne.

Alicja: Dziękuję, Kubo. Myślę, że teraz każdy, kto następnym razem weźmie karty do ręki, uśmiechnie się i pomyśli o złożoności O(n²).

Jakub: Oby! I mam nadzieję, że dzięki temu lepiej zrozumieją, że kiedy potrzebujemy naprawdę dużej wydajności, musimy sięgnąć po inne, potężniejsze narzędzia. Ale o tym opowiemy już w następnym odcinku.

Alicja: Okej, to wszystko ma sens. Ale pomówmy o wydajności. Jak szybki... albo jak wolny... potrafi być ten algorytm?

Jakub: Świetne pytanie, bo odpowiedź brzmi: to zależy. I to bardzo. Spójrzmy na złożoność.

Alicja: Zacznijmy od czarnego scenariusza. Kiedy jest najgorzej?

Jakub: Najgorzej jest, gdy tablica jest posortowana... ale w odwrotnej kolejności. Wyobraź sobie . Wtedy dla każdego elementu musimy przejść przez całą posortowaną już część, porównując i przesuwając wszystko po drodze.

Alicja: Brzmi jak mnóstwo pracy.

Jakub: Dokładnie. To daje nam złożoność kwadratową, czyli O(n²). W skrócie, im więcej elementów, tym wolniej działa to w postępie geometrycznym. To jak szukanie jednej książki w bibliotece, gdzie wszystkie regały są kompletnie pomieszane.

Alicja: Rozumiem. A co z najlepszym przypadkiem? Kiedy algorytm może iść na wcześniejszą emeryturę?

Jakub: Dobre określenie! Najlepiej jest, gdy tablica jest już posortowana. Wtedy przy każdej iteracji porównujemy nowy element tylko z jednym, ostatnim z posortowanej części. Pętla wewnętrzna wykonuje tylko jedno porównanie i zero przesunięć.

Alicja: Czyli to złożoność liniowa, O(n)?

Jakub: Dokładnie tak! Algorytm po prostu sprawdza, czy wszystko jest na swoim miejscu i idzie dalej. Super szybko.

Alicja: A więc kluczowy wniosek jest taki, że wydajność sortowania przez wstawianie dramatycznie zależy od tego, jak bardzo pomieszane są dane na starcie. Od O(n) do O(n²).

Jakub: Właśnie. To jego największa siła i jednocześnie słabość.

Alicja: Niesamowite, jak wiele kryje się za prostymi algorytmami. Jakub, dziękuję ci za kolejną fantastyczną dawkę wiedzy. To już wszystko w dzisiejszym odcinku Studyfi Podcast.

Jakub: Cała przyjemność po mojej stronie. Dzięki za słuchanie i do usłyszenia!

Alicja: Cześć!