Pouze tento týden sleva až 80 % na e-learning týkající se C# .NET. Zároveň využij akci až 30 % zdarma při nákupu e-learningu - 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.

Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

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

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 Čápka
Avatar
Uživatelské hodnocení:
36 hlasů
David je zakladatelem ITnetwork a programování se profesionálně věnuje 13 let. Má rád Nirvanu, sushi 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

 

 

Komentáře
Zobrazit starší komentáře (5)

Avatar
Luboš Běhounek Satik:1.6.2013 12:08

Ze kdyz hledas, kam prvek zaradit, tak nejedes prvek po prvku, ale binarnim pulenim hledas, kam ten prvek prijde - podobne jako treba kdyz hadas nahodne cislo od 0-100, tak ti vzdy staci asi 8 pokusu, abys to uhad, nemusis prochazet vsechny cisla postupne :)

Odpovědět
1.6.2013 12:08
https://www.facebook.com/peasantsandcastles/
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Luboš Běhounek Satik
David Čápka:1.6.2013 12:19

Já vím co je binární hledání ;-)

Odpovědět
1.6.2013 12:19
One of the most common causes of failure is the habit of quitting when one is overtaken by temporary defeat.
Avatar
jigfreed
Člen
Avatar
jigfreed:2.6.2013 1:33
:D
 
Odpovědět
2.6.2013 1:33
Avatar
Neaktivní uživatel:10.1.2017 18:46

Optimalizovaný insertion sort pre PHP:

function insertionDesc($input) {

    $arrayLength = sizeof($input);

    $j = 1;
    while($j < $arrayLength) {

        $key = $input[$j];
        $i = $j - 1;

        while($i > -1) {

            if($input[$i] < $key) {

                $input[$i + 1] = $input[$i];
                $input[$i] = $key;
                --$i;

            } else break;

        }

        ++$j;

    }

    return $input;

}

Pre opačné poradie stačí prehodiť podmienku.

Odpovědět
10.1.2017 18:46
Neaktivní uživatelský účet
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:30.6.2017 13:23

1.

Js kod - je to trosku slozitejsi, protoze to kopiruji z testvaciho scriptu

function sortInsert_1a(cmp,start,end)
{
//arr[1] = [6,5,4,3,2,1]
var cycles = 0;
var start = typeof(start)=='undefined' ? 0         : start;
var end   = typeof(end)  =='undefined' ? arr_count : end;
//alert([start, end])
var i,j, tmp;
    for (i=start+1; i<end; i++) // dulezite je pouzit promennou, pole.lenght by kontroloval v kazdem cyklu
        {
        tmp = arr[1][i];
        j = i-1;
        while (j>=start && cmp(arr[1][j],tmp)>0) // cmp porovnava dve cisla, vraci 1, -1, 0; soucasne loguje log_cmp++
           {
            arr[1][j+1] = arr[1][j];
            j--;
cycles++;
           }
        arr[1][j+1] = tmp;
        }
mm.data.cycles[mm.data.i] += cycles; // log_cycles++
return 1;
}

2. Mozna bych doplnil, ze pro vkladani je mozne polohu urcovat jako stred leve a prave strany, mid = left + (right-left>>1). Tim se stane z inserts-rtu algoritmus s nejmensim poctem cmp operaci. A pouziva to hybrid Tim sort.

        mid_sub = right - left;
        while (true)
                {
                cycles++;
                mid = left + (mid_sub>>1);
                if (cmp(arr[m][j],arr[m][mid])>=0)
                        {
                        left  = mid;
                        mid_sub = right - left;
                        if (mid_sub==1) {mid++; break;}
                        }
                else    {
                        right = mid;
                        mid_sub = right - left;
                        if (mid_sub==1) {break;}
                        }
                }
// tady je zas vyhodnejsi pouzit if-else kvuli rychlosti. procesor nemusi skakat v pameti a ukonci to primo v ifu.

http://mlich.zam.slu.cz/…sorting3.htm - XsortInsertMid­dle_1a...

3. hlavni problem toho algoritmu je, ze se prvek vklada do stale vetsiho pole a cele se musi posunovat. Coz pc nezvladaji. Proto to Timsort kombinuje se slevanim. Jinak lepsi algoritmus neni.

 
Odpovědět
30.6.2017 13:23
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
Elektron
Člen
Avatar
Elektron:9.1.2018 9:04

Snad ten rozdíl už jde dostatečně pochopit. https://www.youtube.com/watch?…

 
Odpovědět
9.1.2018 9:04
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:24.4.2018 16:04

Jeste bych to mozna vysvetlil, jak to funguje.
Klasicky insert: 12, 123 - porovna 3 s 1 i 2, 1234 - porovna 4 a 1, 2 a 3, ...
Insert to middle: 12, 123 - porovna 3 s 1 i 2, 1234 - porovna 2 a pak s 1 nebo 3 (uprostred pole je 2 a od ni se pak hleda stred doleva nebo doprava; cili, neni treba porovnavat vse a misto O(n*n) je slozitost je tusim n * log(n) a mene)
Nevyhoda je, ze pri velkem poli se vklada treba na zacatek pole a n-1 prvku se musi posunout v obou algoritmech. Jinak by slo o nejrychlejsi.

 
Odpovědět
24.4.2018 16:04
Avatar
marek popl
Člen
Avatar
marek popl:12.10.2018 11:01

Insertion sort pro python

a = [16, 19, 11, 15, 10, 12, 14]

for i in a:
    j = a.index(i)

    while j>0:

        if a[j-1] > a[j]:

            a[j-1],a[j] = a[j],a[j-1]
        else:

            break
        j = j-1
print (a)
 
Odpovědět
12.10.2018 11:01
Avatar
Patrik Pastor:18.4.2019 22:54

a jak se prevadi pismeno (index v abecede) na cislo? (k porovnani v algoritmu)? jak by to v c# asi vypadalo, dik

 
Odpovědět
18.4.2019 22:54
Avatar
Peter Mlich
Člen
Avatar
Odpovídá na Patrik Pastor
Peter Mlich:8. dubna 10:57

Uplne nerozumim tve otazce. Znaky typu char a string jsou binarni cisla ascii tabulky, pismeno A ma tusim 65 hex. V prog. jazyku bud pracujes s cislem nebo jako char. Obvykle to neprevadis. Kdyz, slouzi na to obvykle funkce ord() a chr().

 
Odpovědět
8. dubna 10:57
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 15. Zobrazit vše