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(n²) a začíná zaostávat za algoritmy chytřejšími.

Vlastnosti algoritmu

Časová složitost	O(n²)
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ů:

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

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

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

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

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.

Paměť: 1

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ě.

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

Paměť: 4

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

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

{PHP}
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;
  }
}


$list = [17, 14, 4, 18, 2, 8, 2, 20];
insertionSort($list);
print_r($list);

{/PHP}

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.

Článek pro vás napsal David Hartinger

Uživatelské hodnocení:

141 hlasů

David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.

David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.

Aktivity

Nejčastěji vyhledáváné

Lekce 3 - Insertion sort

Vlastnosti algoritmu

Průběh

Vizualizace

Video ukázka

Zdrojový kód