Zaradenie a popis
Insertion Sort je triediaci algoritmus, ktorý realizuje triedenie priamym vkladaním.
Vychádza z predpokladu, že do už utriedenej postupnosi sa na správne miesto vloží ďalší prvok.
Ak sa miesto, na ktoré sa nový prvok vkladá zisťuje binárnym vyhľadávaním,
hovoríme o triedení binárnym vkladaním.
Motivácia a špecifikácia
Máme v poli uloženú postupnosť prvkov. Cieľom je usporiadať túto postupnosť vzostupne.
Vstup: pole A, ktoré je naplnené náhodnými hodnotami
Výstup: utriedené pole A
Myšlienka algoritmu
Prvky sa rozdelia na dve postupnosti: zdrojovú a cieľovú. Za predpokladu, že cieľová postupnosť
dĺžky i je už utriedená, vsunie sa ďalší prvok zo zdrojovej postupnosti na správne miesto a
vznikne utriedená cieľová postupnosť dĺžky i+1. Algoritmus začína s hodnotou indexu 2 (tj.
prvý prvok je utriedený, keďže je jediný) a v rámci každeho kroku sa jeho hodnota zväčší o jednotku.
Pri hľadaní vhodného miesta v cieľovej postupnosti je účelné striedať porovnania prvkov s ich presunmi.
Prvok x sa dostane na svoje miesto tak, že ho porovnáme s jeho ľavým susedom y.
Ak je väčší, tak toho suseda posunieme o jedno miesto vpravo. Proces končí, ak je ďalší prvok väčší ako x,
alebo sme dosiahli koniec cieľovej postupnosti.
Vizualizácia
X-ová súradnica znázorňuje hodnotu prvku, Y-ová súradnica umiestnenie v poli.
Postupne sa do utriedenej postupnosti vkladajú na správne miesta nové prvky.
Autor: Nuno Nogueira, zdroj: www.wikipedia.org
Zápis algoritmu
procedure InsertionSort(var A: array of Integer);
var
i, j, x: Integer;
begin
for i := 2 to High(A) do begin
x:=A[i];
a[0]:=x;
j:=i-1;
while x<A[j] do begin
a[j+1]:=a[j];
j:=j-1;
end;
a[j+1]:=x;
end;
^ TOP
Vlastnosti algoritmu
Časová zložitosť algoritmu je v priemernom prípade je n2/4.
V najhoršom prípade je časová zložitosť tiež O(n2).
Algoritmus pracuje in situ, je stabilný a pracuje online - tredi prvky tak ako prichádzajú na vstup.
Je vhodný na triedenie už čiastočne utriedených postupností, v tomto prípade je časová zložitosť O(n + d) ,
kde d je počet inverzií.
Experimentovanie
Department of Computer Science, University of British Columbia, Canada
Java applety rôznych triediacich algoritmov.
http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
School of Computer Science, Carnegie Mellon University, USA
Grafické znázornenie Insertion sortu.
http://www.cs.cmu.edu/~jaharris/applets/sorting/insert/insertsort.htm