Insertion sort

Algoritmy Třídění Insertion sort

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

 

  Aktivity (1)

Článek pro vás napsal David Čápka
Avatar
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 se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.

Jak se ti líbí článek?
Celkem (6 hlasů) :
55555


 


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

 

 

Komentáře

Avatar
Mircosoft
Redaktor
Avatar
Mircosoft:

Výhoda insertsortu je, že se dá celkem jednoduše použít i na seznamy, které teprve vytváříme - třeba když uživatel zadává slova a program je má průběžně ukládat v abecedním pořadí. Pak to, co už máme, považujeme za setříděnou část, a nesetříděnou část představuje jenom ta jedna zadaná hodnota.

 
Odpovědět  +1 21.7.2011 10:08
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Mircosoft
David Čápka:

Nad tím jsem nikdy nepřemýšlel, je to jistě dobrá vlastnost :)

Odpovědět 21.7.2011 10:19
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
jigfreed
Člen
Avatar
jigfreed:

Místo "držení" prvku v paměti by přece šlo oba prvky prohodit, tak jako se tomu děje u bublinkové a selection sortu, nebo je v tom nějakej problém?

 
Odpovědět 31.5.2013 16:16
Avatar
Luboš Běhounek (Satik):

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
:)
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na jigfreed
David Čápka:

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
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Odpovídá na David Čápka
Luboš Běhounek (Satik):

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
:)
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Čápka:

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

Odpovědět 1.6.2013 12:19
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
jigfreed
Člen
Avatar
 
Odpovědět 2.6.2013 1:33
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 8 zpráv z 8.