Insertion sort – algoritmus s šikovnými prsty

10 Nov

Mezi řadícími algoritmy je Insertion sort králem v jednoduchosti. Je založený na myšlence postupného posouvání všech prvků v poli na správné místo v již seřazené posloupnosti. Každý prvek se posouvá k počátku tak dlouho, dokud před ním není prvek menší. Díky této metodě dokáže na malých polích (řádově desítky prvků) díky své jednoduchosti předběhne i QuickSort. 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. Vylepšením Insertion sortu je výkonnější, ale nestabilní, Shell sort.

Animovaný simulace fungování Insertion sortu - Wikipedie

Insertion sort nahlíží na pole jako na 2 rozdělené čá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.

Příklad fungování:

5 2 3 9 1 Toto pole chceme seřadit insertion sortem.
5 2 3 9 1 První prvek je seřazen.
5 (2) 3 9 1 Číslo 2 < 5, takže posuneme 5 a 2 vložíme před ní.
2 5 3 9 1 Dvě čísla jsou již seřazená.
2 5 (3) 9 1 Číslo 3 < 5, ale 3 > 2, takže posuneme 5 a 3 vložíme před ní.
2 3 5 9 1 Tři čísla jsou již seřazená.
2 3 5 (9) 1 Číslo 9 > 5, takže ho nebudeme posouvat.
2 3 5 9 1 Čtyři čísla jsou již seřazená.
2 3 5 9 (1) Číslo 1 < 9, 1 < 5, 1 < 3, 1 < 2, takže posuneme 2359 a 1 vložíme před ně.
1 2 3 5 9 Pole je seřazeno.

Vizualizace

A ještě krátké video:

 

Zdroje:
http://www.algoritmy.net/article/8/Insertion-sort
http://www.islandsoft.cz/index.php?art=algoritmus-insertion-sort-trideni-cisel-podle-velikosti
http://cs.wikipedia.org/wiki/Insertion_sort

One Response to “Insertion sort – algoritmus s šikovnými prsty”

Trackbacks/Pingbacks

  1. Shell sort « semivt - November 14, 2011

    […] sort funguje na principu Insert sortu, je ovšem výkonnější. Nevýhodou Shell sortu je, že nezachovává pořadí položek s […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: