Sortowanie przez wstawianie w Pythonie i C++

Sortowanie przez wstawianie (ang. insertion sort) to sposób, w jaki większość ludzi układa karty w ręce: bierze kolejną kartę i wsuwa ją między już ułożone, w odpowiednie miejsce. Algorytm jest prosty, sortuje w miejscu i świetnie radzi sobie z danymi, które są już prawie posortowane. Z tego powodu bywa używany jako część szybszych algorytmów sortowania dla krótkich fragmentów danych.

Na tej stronie znajdziesz ideę algorytmu, kod w Pythonie i C++, tabelę przebiegów, zachowanie dla danych prawie posortowanych oraz porównanie z sortowaniem bąbelkowym i przez wybieranie. Każdy przykład przejdziesz krok po kroku w kursie Algorytmy z podstawy programowej: w przeglądarce, bez instalowania niczego i bez konta, z podglądem zmiennych w każdym kroku.

Przejdź sortowanie przez wstawianie krok po kroku

Idea: wsuń kartę na miejsce

Lista dzieli się na część posortowaną z lewej i nieposortowaną z prawej. Na starcie posortowana część to tylko pierwszy element (jeden element zawsze jest posortowany). Dla każdego kolejnego elementu, od indeksu 1:

1. Zapamiętaj go w zmiennej klucz. Jego miejsce w liście może być teraz nadpisane.
2. Idź w lewo po posortowanej części (indeks j). Dopóki element dane[j] jest większy od klucza, przesuń go o jedno miejsce w prawo.
3. Gdy trafisz na element nie większy od klucza (albo dojdziesz do początku listy), wstaw klucz na miejsce j + 1.

Po każdym obrocie zewnętrznej pętli posortowana część rośnie o jeden element. W odróżnieniu od sortowania przez wybieranie elementy z lewej nie są jeszcze na swoich ostatecznych miejscach: późniejszy, mniejszy klucz może je przesunąć.

Sortowanie przez wstawianie w Pythonie

dane = [12, 11, 13, 5, 6]
for i in range(1, len(dane)):
    klucz = dane[i]
    j = i - 1
    while j >= 0 and dane[j] > klucz:
        dane[j + 1] = dane[j]
        j -= 1
    dane[j + 1] = klucz
    print("wstawiono", klucz, dane)

wstawiono 11 [11, 12, 13, 5, 6]
wstawiono 13 [11, 12, 13, 5, 6]
wstawiono 5 [5, 11, 12, 13, 6]
wstawiono 6 [5, 6, 11, 12, 13]

Kolejność warunków w while ma znaczenie: najpierw j >= 0, potem dane[j] > klucz. Gdy j spadnie do -1, pierwszy warunek jest fałszywy i Python nie sprawdza już drugiego. Gdyby sprawdził, dane[-1] oznaczałoby w Pythonie ostatni element listy, a w C++ odczyt spoza tablicy.

Tabela przebiegów

Prześledźmy listę [12, 11, 13, 5, 6]:

Klucz 13 był większy od wszystkiego przed nim, więc pętla while nie wykonała ani jednego obrotu i 13 zostało na miejscu. Klucz 5 był najmniejszy, więc przeszedł na sam początek. Razem 7 przesunięć: tyle, ile lista ma par w złej kolejności (inwersji).

Krokuj ten przykład i patrz, jak j cofa się w lewo

Dane prawie posortowane

Największa zaleta tego algorytmu: gdy lista jest prawie posortowana, wewnętrzna pętla prawie się nie wykonuje. Policzmy przesunięcia:

def wstawianie(dane):
    przesuniecia = 0
    for i in range(1, len(dane)):
        klucz = dane[i]
        j = i - 1
        while j >= 0 and dane[j] > klucz:
            dane[j + 1] = dane[j]
            j -= 1
            przesuniecia += 1
        dane[j + 1] = klucz
    return przesuniecia


print(wstawianie([1, 2, 4, 3, 5, 6, 7, 8]))
print(wstawianie([8, 7, 6, 5, 4, 3, 2, 1]))

1
28

Lista z jedną zamienioną parą potrzebuje jednego przesunięcia. Lista odwrócona to najgorszy przypadek: każdy element wędruje na sam początek, razem 1 + 2 + … + 7 = 28 = n(n-1)/2 przesunięć.

Krokuj przykład z danymi prawie posortowanymi

Sortowanie przez wstawianie w C++

W C++ tablicę przekazujemy do funkcji razem z rozmiarem. Operator && też sprawdza warunki od lewej i przerywa przy pierwszym fałszu, więc kolejność j >= 0 && t[j] > klucz chroni przed odczytem t[-1]:

#include <iostream>
using namespace std;

void wstawianie(int t[], int n) {
  for (int i = 1; i < n; i++) {
    int klucz = t[i];
    int j = i - 1;
    while (j >= 0 && t[j] > klucz) {
      t[j + 1] = t[j];
      j--;
    }
    t[j + 1] = klucz;
  }
}

int main() {
  int t[5] = {12, 11, 13, 5, 6};
  wstawianie(t, 5);
  for (int i = 0; i < 5; i++) {
    cout << t[i] << endl;
  }
  return 0;
}

5
6
11
12
13

Jeden obrót zewnętrznej pętli to osobna, przydatna operacja: wstawienie liczby do posortowanej tablicy. Dopisujemy liczbę na koniec i przesuwamy ją w lewo na właściwe miejsce, bez sortowania całości:

#include <iostream>
using namespace std;

int main() {
  int t[6] = {3, 8, 12, 20, 25, 0};
  int n = 5;
  int x = 17;
  int j = n - 1;
  while (j >= 0 && t[j] > x) {
    t[j + 1] = t[j];
    j--;
  }
  t[j + 1] = x;
  n++;
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      cout << " ";
    }
    cout << t[i];
  }
  cout << endl;
  return 0;
}

3 8 12 17 20 25

Ćwicz: wstaw liczbę do posortowanej listy

Złożoność i porównanie z innymi sortowaniami

Sortowanie przez wstawianie ma złożoność O(n²) w przypadku pesymistycznym i średnim, O(n) w optymistycznym (lista posortowana) i O(1) pamięci dodatkowej. Tabela pokazuje liczbę porównań i przesunięć (dla pozostałych: zamian) dla list 8-elementowych; sortowanie bąbelkowe w wersji z flagą:

Przesunięć jest tyle samo co zamian w sortowaniu bąbelkowym, bo oba algorytmy usuwają jedną inwersję naraz. Wstawianie zwykle potrzebuje jednak mniej porównań, a jedno przesunięcie to jedno przypisanie zamiast trzech. Sortowanie przez wybieranie zawsze porównuje n(n-1)/2 razy, ale zamian robi najmniej. Z tej trójki sortowanie przez wstawianie jest zwykle najszybsze, szczególnie na danych prawie posortowanych.

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Sortowanie przez wstawianie

Specyfikacja. Dane: tablica T[1..n]. Wynik: tablica T posortowana rosnąco.

Lista kroków:

1. Wczytaj n i tablicę T[1..n]. Ustaw i = 2.
2. Jeśli i > n, wypisz T i zakończ.
3. Zapamiętaj x = T[i] i ustaw j = i - 1.
4. Dopóki j ≥ 1 i T[j] > x: przepisz T[j] na miejsce T[j + 1] i zmniejsz j o 1.
5. Wstaw x na miejsce T[j + 1]. Zwiększ i o 1 i wróć do kroku 2.

Pseudokod:

wczytaj n, T
dla i = 2, 3, ..., n wykonuj
  x ← T[i]
  j ← i - 1
  dopóki j ≥ 1 i T[j] > x wykonuj
    T[j + 1] ← T[j]
    j ← j - 1
  T[j + 1] ← x
wypisz T

Schemat blokowy:

Drzewo decyzyjne sortowania trzech liczb. Drzewo pokazuje wszystkie możliwe przebiegi algorytmu dla trzech różnych liczb a, b, c ułożonych w tablicy w tej kolejności. Każdy węzeł to porównanie wykonane przez algorytm, a liść to ustalona kolejność od najmniejszej liczby. Algorytm wykonuje od 2 do 3 porównań.

Najczęstsze błędy

• Brak zmiennej klucz. Pierwsze przesunięcie dane[j + 1] = dane[j] nadpisuje miejsce, na którym stał wstawiany element. Trzeba go zapamiętać wcześniej, a w warunku porównywać z klucz, nie z dane[i].
• Odwrócona kolejność warunków. dane[j] > klucz and j >= 0 przy j = -1 w Pythonie porównuje z ostatnim elementem listy (błędny wynik), a w C++ czyta pamięć przed tablicą. Najpierw j >= 0.
• Wstawienie na j zamiast na j + 1. Pętla kończy się na elemencie nie większym od klucza, więc klucz idzie tuż za nim.
• Zamiana zamiast przesunięcia. Algorytm z zamianami sąsiadów też sortuje, ale robi trzy przypisania tam, gdzie wystarcza jedno.
• Pętla zewnętrzna od 0. Element o indeksie 0 sam tworzy posortowaną część; zaczynamy od i = 1.

Ćwicz w przeglądarce

W temacie “Sortowanie przez wstawianie” kursu Algorytmy z podstawy programowej czekają dwa przykłady do krokowania i trzy zadania, które sprawdzają się automatycznie po uruchomieniu:

• sortowanie przez wstawianie rosnąco (własna funkcja, bez sort() i sorted()),
• wstaw liczbę do posortowanej listy,
• porównanie trzech sortowań (wybieranie, bąbelkowe i wstawianie na kopiach tej samej listy).

Przycisk Krok wykonuje jedną linię, a panel obok pokazuje aktualne wartości i, j, klucz i całej listy, więc widać, jak elementy przesuwają się o jedno miejsce. W wersji z funkcją Krok wchodzi do jej środka, a stos wywołań pokazuje, skąd została wywołana. Dalsze algorytmy z tego samego kursu: wyszukiwanie liniowe i binarne oraz liczby pierwsze i sito Eratostenesa. Pełna lista: algorytmy z podstawy programowej.

Dla nauczycieli

Sortowanie przez wstawianie zamyka szkolną trójkę prostych sortowań. Zadanie z porównaniem trzech algorytmów na tej samej liście pozwala uczniom samodzielnie zmierzyć, który wykonuje najmniej pracy i dla jakich danych. W BitWizards przydzielasz kurs klasie, udostępniasz tematy stopniowo i widzisz przebieg pisania kodu każdego ucznia (podgląd na żywo i odtwarzanie historii). Platforma jest darmowa dla szkół - jak zacząć. Więcej o tym, gdzie algorytmy leżą w podstawie programowej: informatyka w szkole.