Sortowanie przez wstawianie (insertion sort)

Podcast

Algorytmiczne Porządki: Od Kart do Kodu0:00 / 11:16

0:001:00 pozostało

1x

Algorytmy sortowania stanowią fundament informatyki, a jednym z najprostszych do zrozumienia i zaimplementowania jest sortowanie przez wstawianie (insertion sort). Jeśli zastanawiasz się, jak uporządkować dane w efektywny sposób, ten algorytm to doskonały punkt wyjścia. Pomoże Ci on zrozumieć podstawy porządkowania elementów w tablicy.

Sortowanie przez wstawianie (insertion sort) – wprowadzenie

Sortowanie przez wstawianie to algorytm porównawczy, który porządkuje elementy w zbiorze, na przykład w tablicy, w określonej kolejności (rosnącej lub malejącej). Jest to metoda często wykorzystywana w edukacji do wprowadzenia w świat algorytmów sortowania. Ponadto, znajduje praktyczne zastosowanie w sortowaniu małych zbiorów danych lub jako część bardziej złożonych algorytmów, takich jak introsort.

Sortowanie przez wstawianie (insertion sort) – zasada działania

Najłatwiej zrozumieć sortowanie przez wstawianie, posługując się analogią do układania kart w ręku. Wyobraź sobie, że masz już posortowane karty w jednej ręce, a w drugiej stos kart do posortowania. Bierzesz kolejno po jednej karcie ze stosu i wstawiasz ją w odpowiednie miejsce wśród już posortowanych kart.

Jeśli to konieczne, przesuwasz inne karty, aby zrobić miejsce dla nowej. Ten proces powtarza się, aż wszystkie karty zostaną wstawione i posortowane. Algorytm dzieli tablicę na dwie części: posortowaną i nieposortowaną.

Początkowo posortowana część zawiera tylko pierwszy element tablicy, ponieważ pojedynczy element jest zawsze posortowany. Reszta tablicy stanowi część nieposortowaną. W każdej iteracji algorytm pobiera pierwszy element z części nieposortowanej (nazywany „kluczem”) i wstawia go w odpowiednie miejsce w części posortowanej. Aby to zrobić, porównuje klucz z elementami w części posortowanej, przesuwając większe elementy o jedną pozycję w prawo, aż znajdzie właściwe miejsce dla klucza.

Sortowanie przez wstawianie (insertion sort) – pseudokod

Oto pseudokod algorytmu sortowania przez wstawianie dla tablicy A o długości n (indeksowanej od 0 do n-1):

PROCEDURA SortowaniePrzezWstawianie(A, n):
 DLA i OD 1 DO n-1:
 klucz = A[i]
 j = i - 1
 DOPÓKI j >= 0 ORAZ A[j] > klucz:
 A[j + 1] = A[j]
 j = j - 1
 A[j + 1] = klucz
KONIEC PROCEDURY

Wyjaśnienie pseudokodu insertion sort

1. Pętla zewnętrzna DLA i OD 1 DO n-1: Ta pętla iteruje przez każdy element tablicy, począwszy od drugiego elementu (indeks 1), aż do ostatniego. Każdy element A[i] jest traktowany jako „klucz”, który ma zostać wstawiony do już posortowanej części tablicy A[0...i-1]. Pierwszy element A[0] jest uznawany za już posortowany.
2. klucz = A[i]: Bieżący element z nieposortowanej części jest przechowywany w zmiennej klucz. Jest to element, który będzie wstawiany.
3. j = i - 1: Zmienna j wskazuje na ostatni element w aktualnie posortowanej części tablicy.
4. Pętla wewnętrzna DOPÓKI j >= 0 ORAZ A[j] > klucz: Ta pętla przesuwa elementy w posortowanej części tablicy. Porównuje klucz z elementami A[j] (idąc od prawej do lewej w posortowanej części). Jeśli A[j] jest większe od klucza, oznacza to, że A[j] musi zostać przesunięte w prawo, aby zrobić miejsce dla klucza.
5. A[j + 1] = A[j]: Element A[j] jest przesuwany o jedną pozycję w prawo.
6. j = j - 1: Wskaźnik j jest zmniejszany, aby przejść do poprzedniego elementu w posortowanej części.
7. A[j + 1] = klucz: Gdy pętla wewnętrzna się zakończy (czyli znajdziemy element mniejszy lub równy kluczowi, albo dojdziemy do początku tablicy), oznacza to, że znaleźliśmy właściwe miejsce dla klucza. klucz jest wstawiany na pozycję j + 1.

Sortowanie przez wstawianie (insertion sort) – przykład działania

Rozważmy tablicę A = [5, 2, 4, 6, 1, 3].

Krok 0: Początkowa tablica [5, 2, 4, 6, 1, 3]

• Posortowana część: [5]
• Nieposortowana część: [2, 4, 6, 1, 3]

Krok 1: i = 1 (klucz = 2)

• klucz = A[1] = 2
• j = 0
• Porównujemy A[0] (czyli 5) z kluczem (2). 5 > 2, więc przesuwamy 5 w prawo. Tymczasowo: [5, 5, 4, 6, 1, 3].
• j staje się -1. Pętla wewnętrzna kończy się.
• Wstawiamy klucz (2) na pozycję j + 1 = 0. Rezultat: [2, 5, 4, 6, 1, 3].
• Posortowana część: [2, 5]
• Nieposortowana część: [4, 6, 1, 3]

Krok 2: i = 2 (klucz = 4)

• klucz = A[2] = 4
• j = 1
• Porównujemy A[1] (czyli 5) z kluczem (4). 5 > 4, więc przesuwamy 5 w prawo. Tymczasowo: [2, 5, 5, 6, 1, 3].
• j staje się 0.
• Porównujemy A[0] (czyli 2) z kluczem (4). 2 < 4, więc nie przesuwamy. Pętla wewnętrzna kończy się.
• Wstawiamy klucz (4) na pozycję j + 1 = 1. Rezultat: [2, 4, 5, 6, 1, 3].
• Posortowana część: [2, 4, 5]
• Nieposortowana część: [6, 1, 3]

Krok 3: i = 3 (klucz = 6)

• klucz = A[3] = 6
• j = 2
• Porównujemy A[2] (czyli 5) z kluczem (6). 5 < 6, więc nie przesuwamy. Pętla wewnętrzna kończy się.
• Wstawiamy klucz (6) na pozycję j + 1 = 3. Rezultat: [2, 4, 5, 6, 1, 3] (element jest już na właściwej pozycji).
• Posortowana część: [2, 4, 5, 6]
• Nieposortowana część: [1, 3]

Krok 4: i = 4 (klucz = 1)

• klucz = A[4] = 1
• j = 3
• Porównujemy A[3] (czyli 6) z kluczem (1). 6 > 1, przesuwamy 6. Tymczasowo: [2, 4, 5, 6, 6, 3].
• j staje się 2.
• Porównujemy A[2] (czyli 5) z kluczem (1). 5 > 1, przesuwamy 5. Tymczasowo: [2, 4, 5, 5, 6, 3].
• j staje się 1.
• Porównujemy A[1] (czyli 4) z kluczem (1). 4 > 1, przesuwamy 4. Tymczasowo: [2, 4, 4, 5, 6, 3].
• j staje się 0.
• Porównujemy A[0] (czyli 2) z kluczem (1). 2 > 1, przesuwamy 2. Tymczasowo: [2, 2, 4, 5, 6, 3].
• j staje się -1. Pętla wewnętrzna kończy się.
• Wstawiamy klucz (1) na pozycję j + 1 = 0. Rezultat: [1, 2, 4, 5, 6, 3].
• Posortowana część: [1, 2, 4, 5, 6]
• Nieposortowana część: [3]

Krok 5: i = 5 (klucz = 3)

• klucz = A[5] = 3
• j = 4
• Porównujemy A[4] (czyli 6) z kluczem (3). 6 > 3, przesuwamy 6. Tymczasowo: [1, 2, 4, 5, 6, 6].
• j staje się 3.
• Porównujemy A[3] (czyli 5) z kluczem (3). 5 > 3, przesuwamy 5. Tymczasowo: [1, 2, 4, 5, 5, 6].
• j staje się 2.
• Porównujemy A[2] (czyli 4) z kluczem (3). 4 > 3, przesuwamy 4. Tymczasowo: [1, 2, 4, 4, 5, 6].
• j staje się 1.
• Porównujemy A[1] (czyli 2) z kluczem (3). 2 < 3, więc nie przesuwamy. Pętla wewnętrzna kończy się.
• Wstawiamy klucz (3) na pozycję j + 1 = 2. Rezultat: [1, 2, 3, 4, 5, 6].
• Posortowana część: [1, 2, 3, 4, 5, 6]
• Nieposortowana część: []

Tablica jest posortowana: [1, 2, 3, 4, 5, 6]

Złożoność algorytmu sortowania przez wstawianie

Złożoność algorytmu to miara zasobów (czasu lub pamięci) potrzebnych do jego wykonania w zależności od rozmiaru danych wejściowych n.

Złożoność czasowa insertion sort

Złożoność czasowa sortowania przez wstawianie jest analizowana w trzech przypadkach: najlepszym, najgorszym i średnim.

1. Najgorszy przypadek: O(n²) Występuje, gdy tablica jest posortowana w odwrotnej kolejności (np. [6, 5, 4, 3, 2, 1]). W każdej iteracji pętli zewnętrznej (i), element klucz musi być porównany ze wszystkimi elementami w posortowanej części i wszystkie te elementy zostaną przesunięte. Dla i elementów w posortowanej części, wykonujemy około i porównań i i przesunięć, co sumarycznie daje 1 + 2 +... + (n-1), czyli n(n-1)/2 operacji. Jest to złożoność kwadratowa, oznaczana jako O(n²).

2. Najlepszy przypadek: O(n) Występuje, gdy tablica jest już posortowana (np. [1, 2, 3, 4, 5, 6]). W każdej iteracji pętli zewnętrznej, klucz jest porównywany tylko z ostatnim elementem posortowanej części (A[j]). Ponieważ A[j] będzie zawsze mniejsze lub równe kluczowi (bo tablica jest już posortowana), pętla wewnętrzna wykona tylko jedno porównanie i żadnych przesunięć. Całkowita liczba operacji będzie proporcjonalna do n, co daje złożoność liniową, oznaczaną jako O(n).

3. Średni przypadek: O(n²) Dla losowo uporządkowanych danych, średnia liczba porównań i przesunięć jest również proporcjonalna do n². W praktyce, średni przypadek jest zbliżony do najgorszego przypadku.

Złożoność pamięciowa insertion sort

Sortowanie przez wstawianie to algorytm sortujący „w miejscu” (ang. in-place sort). Oznacza to, że do działania potrzebuje tylko stałej, niewielkiej ilości dodatkowej pamięci, niezależnie od rozmiaru danych wejściowych. Złożoność pamięciowa wynosi O(1).

Stabilność algorytmu sortowania przez wstawianie

Algorytm sortujący jest stabilny, jeśli zachowuje względną kolejność elementów o równych wartościach. Oznacza to, że jeśli w oryginalnej tablicy dwa elementy miały tę samą wartość, ale znajdowały się w różnej kolejności, to po posortowaniu przez stabilny algorytm ich względna kolejność zostanie zachowana.

Sortowanie przez wstawianie jest algorytmem stabilnym. Dzieje się tak, ponieważ w pętli wewnętrznej (DOPÓKI j >= 0 ORAZ A[j] > klucz) elementy są przesuwane tylko wtedy, gdy są ściśle większe od klucza. Jeśli A[j] jest równe kluczowi, pętla wewnętrzna zatrzymuje się, a klucz jest wstawiany po tym elemencie. Dzięki temu elementy o tej samej wartości zachowują swoją pierwotną kolejność.

Zalety i wady sortowania przez wstawianie

Jak każdy algorytm, sortowanie przez wstawianie ma swoje mocne i słabe strony, które należy wziąć pod uwagę przy wyborze odpowiedniej metody sortowania.

Zalety insertion sort

• Prostota implementacji: Algorytm jest łatwy do zrozumienia i zaimplementowania, co czyni go idealnym dla początkujących programistów.
• Efektywność dla małych zbiorów danych: Dla n rzędu kilkudziesięciu elementów, sortowanie przez wstawianie jest często szybsze niż bardziej złożone algorytmy (np. quicksort, mergesort). Dzieje się tak ze względu na mniejsze stałe współczynniki i brak narzutu rekurencji.
• Efektywność dla danych prawie posortowanych: W najlepszym przypadku (dane już posortowane lub prawie posortowane) złożoność czasowa wynosi O(n), co czyni go bardzo szybkim.
• Stabilność: Zachowuje względną kolejność równych elementów.
• Sortowanie w miejscu: Wymaga minimalnej dodatkowej pamięci (O(1)).
• Online: Może sortować listę w miarę napływania nowych elementów.

Wady insertion sort

• Niska efektywność dla dużych, nieposortowanych zbiorów danych: Złożoność O(n²) sprawia, że jest niepraktyczny dla dużych tablic, gdzie algorytmy takie jak quicksort czy mergesort (O(n log n)) są znacznie szybsze.
• Duża liczba przesunięć: W najgorszym przypadku każdy element musi być przesunięty, co generuje wiele operacji zapisu do pamięci.

Typowe błędy i nieporozumienia przy nauce sortowania przez wstawianie

Studenci często popełniają pewne błędy lub mają nieporozumienia dotyczące sortowania przez wstawianie:

1. Błędne warunki pętli wewnętrznej: Częstym błędem jest niewłaściwe ustawienie warunków pętli DOPÓKI, co może prowadzić do błędów indeksowania (wyjście poza zakres tablicy) lub nieprawidłowego sortowania. Zawsze pamiętaj o warunku j >= 0.
2. Niewłaściwe wstawienie klucza: Po zakończeniu pętli wewnętrznej klucz musi zostać wstawiony na pozycję j + 1, a nie j. Wynika to z tego, że pętla wewnętrzna zmniejsza j o jeden po ostatnim przesunięciu.
3. Mylenie stabilności z unikalnością: Stabilność dotyczy zachowania kolejności elementów o równych wartościach, a nie tego, czy wszystkie elementy są unikalne.
4. Niedocenianie przypadku prawie posortowanego: Studenci często skupiają się tylko na złożoności O(n²) i zapominają o znaczącej poprawie wydajności do O(n) dla danych prawie posortowanych, co ma praktyczne zastosowanie.

Obserwacje i eksperymenty w symulacji sortowania przez wstawianie

Symulacja sortowania przez wstawianie pozwala na wizualizację krok po kroku, jak algorytm działa, co jest niezwykle pomocne w zrozumieniu jego mechaniki. Podczas korzystania z symulacji warto zwrócić uwagę na następujące aspekty:

1. Krokowe wstawianie klucza: Obserwuj, jak każdy kolejny element (klucz) jest pobierany z nieposortowanej części i „wędruje” w lewo przez posortowaną część, aż znajdzie swoje właściwe miejsce. Zauważ, jak elementy większe od klucza są przesuwane w prawo, aby zrobić dla niego miejsce.
2. Granica między częścią posortowaną a nieposortowaną: Zwróć uwagę, jak ta granica przesuwa się w prawo z każdą iteracją pętli zewnętrznej, a posortowana część tablicy stopniowo rośnie.
3. Liczba porównań i przesunięć: Spróbuj uruchomić symulację dla różnych układów początkowych danych:

• Tablica posortowana: Zobacz, jak szybko algorytm działa. Pętla wewnętrzna wykonuje tylko jedno porównanie na element, co skutkuje minimalną liczbą operacji. Złożoność jest liniowa, O(n).
• Tablica posortowana w odwrotnej kolejności: Obserwuj, jak wiele porównań i przesunięć jest wykonywanych. Każdy element musi być przesunięty przez całą już posortowaną część. To jest najgorszy przypadek, O(n²).
• Tablica losowa: Zauważ, że liczba operacji jest gdzieś pomiędzy najlepszym a najgorszym przypadkiem, ale nadal bliżej O(n²).
• Tablica prawie posortowana: Zobacz, jak algorytm radzi sobie z danymi, które mają tylko kilka elementów poza kolejnością. Powinien działać znacznie szybciej niż dla danych całkowicie losowych, zbliżając się do O(n).

4. Stabilność: Jeśli symulacja pozwala na użycie elementów o identycznych wartościach, sprawdź, czy ich względna kolejność jest zachowana po sortowaniu. Na przykład, jeśli masz [5a, 2, 5b], po posortowaniu powinno być [2, 5a, 5b], a nie [2, 5b, 5a].

Eksperymentowanie z symulacją dla różnych rozmiarów tablic i różnych układów początkowych danych pomoże utrwalić zrozumienie, kiedy sortowanie przez wstawianie jest efektywne, a kiedy nie, oraz jak jego złożoność czasowa zmienia się w zależności od charakterystyki danych wejściowych.

Sortowanie przez wstawianie (insertion sort) – Często zadawane pytania

Czym jest sortowanie przez wstawianie (insertion sort)?

Sortowanie przez wstawianie to prosty algorytm sortowania, który dzieli tablicę na posortowaną i nieposortowaną część. W każdej iteracji pobiera element z części nieposortowanej i wstawia go w odpowiednie miejsce w części posortowanej.

Jaka jest złożoność czasowa sortowania przez wstawianie?

Złożoność czasowa zależy od stanu początkowego danych. W najlepszym przypadku (dane posortowane) wynosi O(n), natomiast w najgorszym (dane posortowane odwrotnie) i średnim przypadku wynosi O(n²).

Czy sortowanie przez wstawianie jest stabilne?

Tak, sortowanie przez wstawianie jest algorytmem stabilnym. Zachowuje ono względną kolejność elementów o równych wartościach.

Kiedy warto stosować sortowanie przez wstawianie?

Sortowanie przez wstawianie jest efektywne dla małych zbiorów danych oraz dla danych, które są już częściowo posortowane lub prawie posortowane. Jest również łatwe do zaimplementowania i wymaga minimalnej dodatkowej pamięci (O(1)).

Czym różni się złożoność czasowa od pamięciowej?

Złożoność czasowa mierzy, ile czasu algorytm potrzebuje do wykonania w zależności od rozmiaru danych wejściowych. Złożoność pamięciowa natomiast określa, ile dodatkowej pamięci algorytm zużywa. Sortowanie przez wstawianie ma złożoność czasową O(n²) (w ogólnym przypadku) i pamięciową O(1).