Insertion Sort - Czy ten prosty algorytm ma sens w 2024?

Najlepiej rozumieć sortowanie przez wstawianie jako prosty sposób porządkowania danych, w którym każdy kolejny element trafia dokładnie tam, gdzie powinien znaleźć się w już uporządkowanej części tablicy. To jeden z tych algorytmów, które świetnie uczą myślenia o pętlach, warunkach i przesuwaniu elementów, a przy okazji pokazują, dlaczego nie każde rozwiązanie dla danych ma taką samą wydajność. Ja najczęściej tłumaczę go na kartach do gry, bo od razu widać, że chodzi o dokładanie elementu do gotowego układu, a nie o jednorazowe przetasowanie wszystkiego.

Jak działa ten algorytm

Mechanika jest prosta: na początku uznajemy pierwszy element za już uporządkowany, a resztę traktujemy jako część jeszcze nieprzetworzoną. Potem bierzemy kolejny element, porównujemy go z wartościami po lewej stronie i przesuwamy większe elementy o jedno miejsce w prawo, aż znajdziemy właściwe miejsce na wstawienie. Dzięki temu uporządkowany fragment tablicy rośnie o jeden element przy każdej iteracji.

W praktyce ten schemat ma bardzo czytelny rytm:

• wybierasz bieżący element do wstawienia,
• cofasz się przez już uporządkowaną część,
• przesuwasz większe wartości w prawo,
• wstawiasz element w wolne miejsce,
• powtarzasz cały proces dla kolejnego indeksu.

Ta logika jest ważna, bo nie chodzi tu o ciągłe zamienianie wszystkiego z wszystkim. Algorytm nie przebudowuje całej tablicy od nowa, tylko rozszerza fragment, który już jest poprawny. Tę różnicę najlepiej widać na konkretnym przykładzie.

Jak wygląda to na przykładzie liczbowym

Weźmy tablicę [5, 2, 4, 6, 1, 3]. Pierwszy element, czyli 5, traktujemy jako gotowy, posortowany fragment. Potem wstawiamy kolejne wartości, zawsze dbając o to, żeby lewa część pozostała uporządkowana.

To dobry moment, żeby zwrócić uwagę na szczegół, który początkujący często pomijają: tutaj nie wykonuje się klasycznej serii swapów całych par, tylko przesuwa się fragment tablicy w prawo, robiąc miejsce dla nowej wartości. To właśnie sprawia, że algorytm jest tak naturalny do zrozumienia, ale też tak kosztowny, gdy danych jest dużo. Gdy masz już ten obraz, łatwiej będzie Ci przełożyć go na kod.

Jak napisać to w JavaScripcie

W JavaScripcie implementacja jest krótka, ale warto rozumieć, co robi każda linia. Ja zwykle zaczynam od wersji działającej na kopii tablicy, bo dzięki temu łatwiej testować wynik bez niszczenia danych wejściowych. Sam algorytm działa jednak tak samo także w wersji modyfikującej oryginalną tablicę.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j + 1] = key;
  }

  return arr;
}

const data = [5, 2, 4, 6, 1, 3];
const sorted = insertionSort([...data]); // kopia, jeśli chcesz zachować oryginał

Najważniejsze elementy tej wersji są trzy. Po pierwsze, pętlę zewnętrzną zaczynam od indeksu 1, bo pojedynczy element z definicji jest już uporządkowany. Po drugie, w zmiennej key zapisuję wartość, którą chcę wstawić, zanim zacznę przesuwać inne elementy. Po trzecie, warunek arr[j] > key jest istotny dla stabilności: gdy wartości są równe, nie przestawiam ich względem siebie.

Jeśli sortujesz liczby, taki kod wystarczy. Jeśli sortujesz napisy albo obiekty, sama idea pozostaje ta sama, ale porównanie trzeba oprzeć na własnej regule, na przykład na długości tekstu, nazwie albo polu liczbowym. To ważna różnica między nauką algorytmu a użyciem go w realnym projekcie.

Złożoność, pamięć i stabilność

Ten algorytm jest dobrym przykładem na to, że prostota kodu nie oznacza automatycznie wysokiej wydajności. W najlepszym przypadku działa szybko, bo gdy dane są już prawie uporządkowane, pętla wewnętrzna kończy się po jednym porównaniu. W najgorszym przypadku, na przykład przy tablicy odwrotnie posortowanej, każdy nowy element musi przejść przez cały uporządkowany fragment.

Warto znać też pojęcie inwersji, czyli pary elementów ustawionych względem siebie w złej kolejności. Im więcej takich inwersji, tym więcej przesunięć musi wykonać algorytm. To właśnie dlatego na danych prawie posortowanych wypada zaskakująco dobrze, a na losowej lub odwróconej tablicy jego koszt szybko przestaje być atrakcyjny. I właśnie dlatego warto porównać go z prostszymi alternatywami, żeby nie dobrać narzędzia do złego zadania.

Kiedy to rozwiązanie wygrywa, a kiedy przegrywa

Najuczciwsza odpowiedź brzmi: to świetny wybór do małych zbiorów danych, do nauki i do sytuacji, w których wejście jest już częściowo uporządkowane. Jeśli dopisujesz kilka elementów do listy i chcesz utrzymać porządek bez przeliczania wszystkiego od nowa, ten algorytm pasuje bardzo dobrze. W takich warunkach jego prostota naprawdę wygrywa z bardziej rozbudowanymi metodami.

Jeśli porównuję go z sortowaniem bąbelkowym, zwykle wypada lepiej w praktyce, bo wykonuje mniej zbędnych ruchów. Jeśli porównuję go z nowoczesnymi algorytmami ogólnego przeznaczenia, przegrywa wydajnością na większych zbiorach. To nie jest wada konstrukcyjna, tylko informacja o jego naturalnym miejscu: prosty, czytelny, dobry do małych i częściowo uporządkowanych danych.

Najczęstsze błędy przy implementacji

Nawet prosty kod potrafi sprawić kłopot, jeśli przesuniesz jeden indeks w złą stronę albo źle ustawisz warunek pętli. W tej technice błędy zwykle nie są spektakularne, ale dają wyniki, które wyglądają prawie poprawnie, więc łatwo je przeoczyć. To właśnie takie przypadki warto wyłapać od razu.

1. Zły indeks startowy - pętlę zewnętrzną najlepiej zacząć od 1, bo pierwszy element jest już traktowany jako uporządkowany. Start od 0 nie zepsuje wszystkiego, ale jest niepotrzebny.
2. Brak zapisanego elementu tymczasowego - zanim zaczniesz przesuwać dane, zachowaj wartość w zmiennej key. Bez tego zgubisz element, który miał zostać wstawiony.
3. Zły warunek porównania - użycie >= zamiast > może zepsuć stabilność algorytmu, bo równe elementy zaczną zmieniać kolejność.
4. Niepoprawny indeks docelowy - po zakończeniu przesuwania trzeba zapisać element do arr[j + 1], a nie do arr[j].
5. Zastosowanie do złego problemu - ten algorytm świetnie nadaje się do małych lub prawie uporządkowanych danych, ale nie jest dobrym domyślnym wyborem dla dużych, losowych tablic.

Jeśli pracujesz z obiektami, dochodzi jeszcze jedna pułapka: porównywanie musi odnosić się do konkretnej cechy, a nie do całego obiektu. Sam mechanizm pozostaje ten sam, ale logika sortowania musi odzwierciedlać rzeczywistą potrzebę biznesową. Na koniec zostaje jedna rzecz, którą początkujący często przegapiają, a która naprawdę pomaga później w nauce kolejnych algorytmów.

Dlaczego ten prosty schemat nadal warto znać

Najcenniejsze w tej technice nie jest samo porządkowanie liczb, tylko sposób myślenia: najpierw utrzymujesz mały, pewny fragment, a potem rozbudowujesz go o kolejny element bez psucia tego, co już działa. To dokładnie ten sam wzorzec, który później wraca przy pracy z listami w interfejsie, przy aktualizowaniu wyników na żywo i przy wielu prostych algorytmach iteracyjnych.

Jeśli zapamiętasz tylko jedną rzecz, niech będzie taka: to bardzo dobry wybór do małych, prawie uporządkowanych danych i świetny materiał do nauki podstaw programowania, ale nie uniwersalne rozwiązanie do wszystkiego. Gdy zależy Ci na szybkości przy większych zbiorach, lepiej sięgnąć po mocniejsze narzędzie; gdy zależy Ci na zrozumieniu logiki pętli, przesuwania i stabilności, ten algorytm nadal robi wyjątkowo dobrą robotę.