Technikum Klasa I 45 minut PP: I.2c | s. 342

Lekcja 10: Sortowanie przez wstawianie - algorytm

Insertion sort - zasada dzialania, pseudokod, analiza krok po kroku

📋 Podstawa programowa: I.2c
algorytmyinsertion sortsortowanie przez wstawianiezlozonosc
00:00
Wprowadzenie
5 min
00:05
Teoria
18 min
00:23
Cwiczenia
17 min
00:40
Podsumowanie
5 min
📚

Teoria

▼

Czym jest sortowanie?

Sortowanie to uporzadkowanie elementow zbioru wedlug okreslonego kryterium (np. rosnaco, malejaco, alfabetycznie). Jest to jeden z najczesciej wykonywanych operacji w informatyce.

Sortowanie przez wstawianie - intuicja

Sortowanie przez wstawianie dziala tak, jak ukladamy karty w rece podczas gry:

  • Bierzemy kolejna karte z talii (nieposortowanej czesci)
  • Wstawiamy ja na odpowiednie miejsce wsrod kart juz uporzadkowanych
  • Powtarzamy az wszystkie karty beda ulozone
Kluczowa idea: Dzielimy tablice na czesc posortowana (poczatkowo 1 element) i nieposortowana. W kazdym kroku bierzemy pierwszy element z czesci nieposortowanej i wstawiamy go na wlasciwe miejsce w czesci posortowanej.

Algorytm - pseudokod

ALGORYTM SortowaniePrzezWstawianie(T, n):
  // T - tablica, n - liczba elementow
  DLA i OD 1 DO n-1:
    klucz = T[i]           // element do wstawienia
    j = i - 1
    // Przesuwamy elementy wieksze od klucza w prawo
    DOPOKI j >= 0 ORAZ T[j] > klucz:
      T[j+1] = T[j]       // przesun w prawo
      j = j - 1
    T[j+1] = klucz         // wstaw na wlasciwe miejsce

Przyklad krok po kroku

Tablica poczatkowa: [5, 3, 8, 1, 4]

Krok 1 (i=1): klucz=3
  [5, 3, 8, 1, 4]  <- 3 < 5, przesun 5 w prawo
  [3, 5, 8, 1, 4]  <- wstaw 3 na pozycje 0
  Posortowane: [3, 5] | Reszta: [8, 1, 4]

Krok 2 (i=2): klucz=8
  [3, 5, 8, 1, 4]  <- 8 > 5, nic nie przesuwamy
  [3, 5, 8, 1, 4]  <- 8 zostaje na miejscu
  Posortowane: [3, 5, 8] | Reszta: [1, 4]

Krok 3 (i=3): klucz=1
  [3, 5, 8, 1, 4]  <- 1 < 8, przesun 8
  [3, 5, 8, 8, 4]  <- 1 < 5, przesun 5
  [3, 5, 5, 8, 4]  <- 1 < 3, przesun 3
  [3, 3, 5, 8, 4]  <- wstaw 1 na pozycje 0
  [1, 3, 5, 8, 4]
  Posortowane: [1, 3, 5, 8] | Reszta: [4]

Krok 4 (i=4): klucz=4
  [1, 3, 5, 8, 4]  <- 4 < 8, przesun 8
  [1, 3, 5, 8, 8]  <- 4 < 5, przesun 5
  [1, 3, 5, 5, 8]  <- 4 > 3, STOP
  [1, 3, 4, 5, 8]  <- wstaw 4 na pozycje 2

Wynik: [1, 3, 4, 5, 8] - posortowane!

Zlozonosc obliczeniowa

  • Najlepszy przypadek: O(n) - tablica juz posortowana (kazdy element od razu na miejscu)
  • Najgorszy przypadek: O(n^2) - tablica posortowana odwrotnie (kazdy element przesuwa sie na poczatek)
  • Sredni przypadek: O(n^2)

Zalety sortowania przez wstawianie

  • Prosty w implementacji
  • Wydajny dla malych zbiorow danych
  • Wydajny dla danych prawie posortowanych
  • Stabilny - zachowuje kolejnosc rownych elementow
  • Sortuje "w miejscu" - nie wymaga dodatkowej pamieci
✏️

Zadania

▼
Latwe

Zadanie 1: Sortowanie krok po kroku

Posortuj tablice [7, 2, 5, 1, 9, 3] metoda przez wstawianie. Zapisz stan tablicy po kazdym kroku (po kazdym wstawieniu).

Pokaz rozwiazanie 
Poczatek: [7, 2, 5, 1, 9, 3]

i=1, klucz=2: 2<7, przesun 7
  [2, 7, 5, 1, 9, 3]

i=2, klucz=5: 5<7, przesun 7; 5>2, stop
  [2, 5, 7, 1, 9, 3]

i=3, klucz=1: 1<7, przesun 7; 1<5, przesun 5;
              1<2, przesun 2; wstaw 1 na poz. 0
  [1, 2, 5, 7, 9, 3]

i=4, klucz=9: 9>7, stop (zostaje na miejscu)
  [1, 2, 5, 7, 9, 3]

i=5, klucz=3: 3<9, przesun 9; 3<7, przesun 7;
              3<5, przesun 5; 3>2, stop
  [1, 2, 3, 5, 7, 9]

Wynik: [1, 2, 3, 5, 7, 9]
Latwe

Zadanie 2: Sortowanie malejaco

Zmodyfikuj algorytm sortowania przez wstawianie, aby sortowal malejaco (od najwiekszego do najmniejszego). Nastepnie posortuj tablice [4, 8, 2, 6, 1] malejaco.

Pokaz rozwiazanie 
Modyfikacja: zmiana warunku z "T[j] > klucz" na "T[j] < klucz"

ALGORYTM SortowanieMalejaco(T, n):
  DLA i OD 1 DO n-1:
    klucz = T[i]
    j = i - 1
    DOPOKI j >= 0 ORAZ T[j] < klucz:  // zmiana znaku!
      T[j+1] = T[j]
      j = j - 1
    T[j+1] = klucz

Sortowanie [4, 8, 2, 6, 1] malejaco:

i=1, klucz=8: 8>4, przesun 4
  [8, 4, 2, 6, 1]

i=2, klucz=2: 2<4, stop
  [8, 4, 2, 6, 1]

i=3, klucz=6: 6>2, przesun 2; 6>4, przesun 4;
              6<8, stop
  [8, 6, 4, 2, 1]

i=4, klucz=1: 1<2, stop
  [8, 6, 4, 2, 1]

Wynik: [8, 6, 4, 2, 1]
Srednie

Zadanie 3: Liczenie operacji

Policz liczbe porownan i przesuniec dla kazdego przypadku:

a) Tablica juz posortowana: [1, 2, 3, 4, 5]
b) Tablica posortowana odwrotnie: [5, 4, 3, 2, 1]

Pokaz rozwiazanie 
a) [1, 2, 3, 4, 5] - juz posortowana:
   i=1: klucz=2, porownaj z 1: 2>1, stop (1 porownanie, 0 przesuniec)
   i=2: klucz=3, porownaj z 2: 3>2, stop (1 porownanie, 0 przesuniec)
   i=3: klucz=4, porownaj z 3: 4>3, stop (1 porownanie, 0 przesuniec)
   i=4: klucz=5, porownaj z 4: 5>4, stop (1 porownanie, 0 przesuniec)
   RAZEM: 4 porownania, 0 przesuniec -> O(n)

b) [5, 4, 3, 2, 1] - odwrotnie:
   i=1: klucz=4, porownaj z 5: przesun (1 por., 1 przes.)
   i=2: klucz=3, porownaj z 5,4: przesun oba (2 por., 2 przes.)
   i=3: klucz=2, porownaj z 5,4,3: przesun (3 por., 3 przes.)
   i=4: klucz=1, porownaj z 5,4,3,2: przesun (4 por., 4 przes.)
   RAZEM: 10 porownan, 10 przesuniec -> O(n^2)
   (Wzor: n*(n-1)/2 = 5*4/2 = 10)
Trudne

Zadanie 4: Sortowanie tekstow

Uzyj sortowania przez wstawianie do uporzadkowania listy nazwisk alfabetycznie (leksykograficznie). Zapisz kazdy krok:
["Nowak", "Kowalski", "Adamski", "Zielinski", "Borkowski"]

Pokaz rozwiazanie 
Poczatek: ["Nowak", "Kowalski", "Adamski", "Zielinski", "Borkowski"]

i=1, klucz="Kowalski":
  "Kowalski" < "Nowak" (K < N), przesun "Nowak"
  ["Kowalski", "Nowak", "Adamski", "Zielinski", "Borkowski"]

i=2, klucz="Adamski":
  "Adamski" < "Nowak", przesun "Nowak"
  "Adamski" < "Kowalski" (A < K), przesun "Kowalski"
  ["Adamski", "Kowalski", "Nowak", "Zielinski", "Borkowski"]

i=3, klucz="Zielinski":
  "Zielinski" > "Nowak" (Z > N), stop
  ["Adamski", "Kowalski", "Nowak", "Zielinski", "Borkowski"]

i=4, klucz="Borkowski":
  "Borkowski" < "Zielinski", przesun "Zielinski"
  "Borkowski" < "Nowak", przesun "Nowak"
  "Borkowski" < "Kowalski", przesun "Kowalski"
  "Borkowski" > "Adamski" (B > A), stop
  ["Adamski", "Borkowski", "Kowalski", "Nowak", "Zielinski"]

Wynik: ["Adamski", "Borkowski", "Kowalski", "Nowak", "Zielinski"]
🎥

Materialy wideo

▼
Algorytm sortowania wiaderkowego: wizualizacja krok po kroku
Quoc Dat Phung
Algorytmy - Sortowanie szybkie (Quick Sort) [Python]
Kanał o Wszystkim
🎧

Podcasty

▼
✔️

Quiz - sprawdz sie!

▼
📜

Podstawa programowa

▼
← Lekcja 9: Szyfrowanie metoda Cezara Lekcja 11: Sortowanie babelkowe →