Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Lekce 3 - Insertion sort

V minulé lekci, Bubblesort, jsme si ukázali algoritmus Bubblesort i se zdrojovými kódy.

Insertion sort je králem mezi jednoduchými třídícími algoritmy. Je stabilní, jednoduchý na implementaci, chová se inteligentně na již předtříděných polích a na malých polích (řádově desítky prvků) díky své jednoduchosti předběhne i QuickSort.

Insertion sort vidí pole rozdělené na 2 části - setříděnou a nesetříděnou. Postupně vybírá prvky z nesetříděné části a vkládá je mezi prvky v setříděné části tak, aby zůstala setříděná. Od toho jeho jméno - vkládá prvek přesně tam, kam patří a nedělá tedy žádné zbytečné kroky, jako například Bubble sort.

Na větších polích se samozřejmě začně projevovat handicap algoritmu, který spočívá v jeho časové složitosti O(n2) a začíná zaostávat za algoritmy chytřejšími.

Vlastnosti algoritmu

Časová složitost O(n2)
Stabilita Ano
Rychlost Vysoká na malých polích

Pozn. je myšlena časová složitost průměrného případu a rychlost vzhledem ke všem třídícím algoritmům

Průběh

Máme pole následujících prvků:

3 2 5 1 9 4

První prvek (3) budeme považovat za zatříděný a zbytek pole za nesedtříděný. Začneme tedy od druhého prvku (2), který si uložíme do pomocné paměti.

Paměť: 2

3 2 5 1 9 4

Nyní budeme vytvářet místo pro tento prvek v již setříděné části, kam ho poté vložíme. Budeme posouvat prvky v setříděné části pole doprava tak dlouho, dokud buď nenarazíme na prvek menší (nebo stejný) nebo na začátek pole. Trochu matoucí může být, že jeden prvek bude v poli fyzicky zapsán 2x, protože jednou to bude znamenat mezeru (vyznačeno šedou barvou). Z teoretického hlediska je tam prázdno, jak můžete vidět dále na demonstraci algoritmu na videu.

Zpátky k našemu případu - v paměti máme prvek 2, který je jistě menší než prvek 3, proto prvek 3 posuneme doprava. Tím se připravíme o prvek 2, ale ten máme v paměti,takže nám to nijak nevadí.

Paměť: 2

3 3 5 1 9 4

Před vzniklou mezerou je již začátek pole, vložíme tedy na "prázdné" místo prvek z paměti. Setříděná část pole má již tedy 2 prvky.

Paměť: 2

2 3 5 1 9 4

Půjdeme zatřídit další prvek, kterým je nyní prvek 5.

2 3 5 1 9 4

Zjistíme, že je před ním menší číslo, je tedy na správném místě. Velikost setříděné části se opět zvětší. Dalším na řadě bude prvek 1.

2 3 5 1 9 4

Paměť: 1

2 3 5 5 9 4

Paměť: 1

2 3 3 5 9 4

Paměť: 1

2 2 3 5 9 4

Paměť: 1

1 2 3 5 9 4

Zarazil nás až začátek pole, protože žádný jiný prvek nebyl menší než jednička. Prvek 9 očividně zůstane na místě.

1 2 3 5 9 4

Poslední je prvek 4, začneme tedy s posouváním.

1 2 3 5 9 4

Paměť: 4

1 2 3 5 9 9

Paměť: 4

1 2 3 5 5 9

Zastavíme se před prvkem 3 a vložíme prvek 4 z paměti na volné místo. Hotovo :)

1 2 3 4 5 9

Vizualizace

Video ukázka

Zdrojový kód

  • public static void insertionSort(int[] list) {
      int item, j;
      for (int i = 1; i <= (list.length - 1); i++) {
        // ulozeni prvku
        item = list[i];
        j = i - 1;
        while ((j >= 0) && (list[j] > item)) {
          list[j + 1] = list[j];
          j--;
        }
        list[j + 1] = item;
      }
    }
  • public static void insertionSort(int[] list) {
      int item, j;
      for (int i = 1; i <= (list.Length - 1); i++) {
        // ulozeni prvku
        item = list[i];
        j = i - 1;
        while ((j >= 0) && (list[j] > item)) {
          list[j + 1] = list[j];
          j--;
        }
        list[j + 1] = item;
      }
    }
  • // setridi vlozene pole, predpoklada indexovani od 0
    procedure insertion_sort(var list: array of integer)
    var i, j, item: integer;
    begin
      for i:=1 to (length(list) - 1) do begin
        // ulozeni prvku
        item:=list[i];
        j:=i - 1;
        while ((j >= 0) and (list[j] > item)) do begin
          list[j + 1]:=list[j];
          dec(j);
        end;
        list[j + 1]:=item;
      end;
    end;
  • def insertion_sort(list)
      1.upto(list.length - 1) do |i|
        # ulozeni prvku
        item = list[i]
        j = i - 1
        while ((j >= 0) && (list[j] > item))
          list[j + 1] = list[j]
          j -= 1;
        end
        list[j + 1] = item
      end
    end
  • function insertionSort(array &$list) {
      for ($i = 1; $i <= count($list) - 1; $i++) {
        // ulozeni prvku
        $item = $list[$i];
        $j = $i - 1;
        while (($j >= 0) && ($list[$j] > $item)) {
          $list[$j + 1] = $list[$j];
          $j--;
        }
        $list[$j + 1] = $item;
      }
    }
    
    
  • Public Sub InsertionSort(cisla() As Integer)
        Dim cislo As Integer
        Dim j As Integer
        For i As Integer = 0 To cisla.Length - 1
            cislo = cisla(i) ' uložení prvku
            j = i - 1
            While (j >= 0) AndAlso (cisla(j) > cislo)
                cisla(j + 1) = cisla(j)
                j -= 1
            End While
            cisla(j + 1) = cislo
        Next
    End Sub

V další lekci, Heapsort, si ukážeme algoritmus Heapsort i se zdrojovými kódy.


 

Předchozí článek
Bubblesort
Všechny články v sekci
Třídicí/řadicí algoritmy
Přeskočit článek
(nedoporučujeme)
Heapsort
Článek pro vás napsal David Hartinger
Avatar
Uživatelské hodnocení:
121 hlasů
David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.
Unicorn university David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity