Předvánoční Black Friday Předvánoční Black Friday
Až 80% zdarma! Předvánoční BLACK FRIDAY akce. Více informací

Insertion sort

Algoritmy Třídění Insertion sort American English version English version

Unicorn College ONEbit hosting Tento obsah je dostupný zdarma v rámci projektu IT lidem. Vydávání, hosting a aktualizace umožňují jeho sponzoři.

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

Autorem widgetu s vizualizací je Jenkings

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

 

 

Článek pro vás napsal David Čápka
Avatar
Jak se ti líbí článek?
9 hlasů
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor sítě se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.
Miniatura
Předchozí článek
Bubblesort
Miniatura
Všechny články v sekci
Třídící/řadící algoritmy
Miniatura
Následující článek
Heapsort
Aktivity (2)

 

 

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

Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Luboš Satik Běhounek:31.5.2013 17:04

Drobnou upravou se da dostat slozitost na n*log2n, staci pri hledani, kam prvek zaradime, pouzit binarni puleni.

Odpovědět  +1 31.5.2013 17:04
https://www.facebook.com/peasantsandcastles/
Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:1.6.2013 11:40

Myslím, že tu je dostatečně popsané jak to funguje :) Při prohození si prvek uložíš také do paměti, nevím, v čem je rozdíl.

Odpovědět 1.6.2013 11:40
Jsem moc rád, že jsi na síti, a přeji ti top IT kariéru, ať jako zaměstnanec nebo podnikatel. Máš na to! :)
Avatar
Luboš Satik Běhounek
Autoredaktor
Avatar
Odpovídá na David Čápka
Luboš Satik Běhounek: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š Satik Běhounek
David Čápka:1.6.2013 12:19

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

Odpovědět 1.6.2013 12:19
Jsem moc rád, že jsi na síti, a přeji ti top IT kariéru, ať jako zaměstnanec nebo podnikatel. Máš na to! :)
Avatar
jigfreed
Člen
Avatar
jigfreed:2.6.2013 1:33
:D
 
Odpovědět 2.6.2013 1:33
Avatar
Samuel Illo
Redaktor
Avatar
Samuel Illo :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
www.samuelillo.com | www.github.com/lamka02sk
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
Avatar
Elektron
Člen
Avatar
Odpovídá na David Čápka
Elektron:9. ledna 9:04

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

 
Odpovědět 9. ledna 9:04
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:24. dubna 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. dubna 16:04
Avatar
marek popl
Člen
Avatar
marek popl:12. října 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. října 11:01
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 13. Zobrazit vše