Licenca
To delo je na voljo pod pogoji slovenske licence Creative Commons 2.5:
priznanje avtorstva - nekomercialno - deljenje pod enakimi pogoji.
Celotna licenca je na voljo na spletu na naslovu http://creativecommons.org/licenses/by-nc-sa/2.5/si/. V skladu s to licenco je dovoljeno vsakemu uporabniku delo razmnoževati, distribuirati, javno priobčevati, dajati v najem in tudi predelovati, vendar samo v nekomercialne namene in ob pogoju, da navede avtorja oziroma avtorje in izdajatelja tega dela. Če uporabnik delo predela, kar pomeni, da ga spremeni, preoblikuje, prevede ali uporabi to delo v svojem delu, lahko predelavo dela ponudi na voljo le pod pogoji, ki so enaki pogojem iz te licence oziroma pod enako licenco.
Urejanje z vstavljanjem
Recimo, da imamo že neko urejeno zaporedje in želimo vanj vstaviti nov element tako, da bo zaporedje ostalo urejeno. Na primer:
[2, 5, 7, 8 | 3]
Tu imamo torej urejeno zaporedje [2, 5, 7, 8], na koncu pa je še element 3, ki bi ga radi vstavili na ustrezno mesto, tako da bo potem zaporedje kot celota urejeno. Element 3 si zapomnimo, njegovo celico v tabeli pa si za zdaj predstavljajmo kot prazno:
[2, 5, 7, 8, ☐]
Če želimo vstaviti element 3 v zaporedje tako, da bo le-to ostalo urejeno, moramo vse elemente, ki so večji od 3, premakniti za eno mesto naprej. To je koristno početi od desne proti levi. Za začetek vidimo, da je 8 več kot 3, zato ga premaknimo naprej:
[2, 5, 7, ☐, 8]
Tudi 7 je več kot 3 in ga moramo premakniti naprej:
[2, 5, ☐, 7, 8]
Enako tudi 5:
[2, ☐, 5, 7, 8]
Zdaj vidimo, da 2 ni več kot 3, zato moramo element 3 vstaviti za 2 in postopek vstavljanja je končan. Dobili smo urejeno zaporedje:
[2, 3, 5, 7, 8]
Ta postopek vstavljanja je prikladen osnovni gradnik za urejanje poljubnega zaporedja.
Začnimo z nekim neurejenim zaporedjem, recimo [5, 8, 7, 2, 3]. Njegov prvi element si lahko ločeno predstavljamo kot urejeno zaporedje dolžine 1:
[5 | 8, 7, 2, 3]
Navpična črta označuje mejo med urejenim in neurejenim delom. Tik za neurejenim delom je element 8; če ga vstavimo v urejeni del, se le-ta podaljša v [5, 8] in naša tabela dobi obliko:
[5, 8 | 7, 2, 3]
Nato vstavimo element 7 v urejeni del tabele in dobimo:
[5, 7, 8 | 2, 3]
Naslednji element je 2; ko ga vstavimo v urejeni del tabele, nastane:
[2, 5, 7, 8 | 3]
Končno vstavimo v urejeni del tabele še zadnji element, 3 – to vstavljanje je prav tisto, ki smo si ga malo prej ogledali podrobneje – in tabela je v celoti urejena:
[2, 3, 5, 7, 8]
Ta postopek se imenuje urejanje z vstavljanjem (ang. insertion sort).