Urejanje z navadnim vstavljanjem () je stabilen algoritem za urejanje podatkov. Deluje tako, da vzamemo prvi element v neurejenem delu tabele in ga vstavimo na pravo mesto v urejenem delu.
Delovanje
Algoritem doda prvi element v urejeni del tabele, nato pa se iterativno premika na naslednji neurejen element in ga vstavi na ustrezno mesto v urejeni del. Iskanje ustreznega mesta za vstavljanje v urejeni del lahko implementiramo na več načinov, npr. z bisekcijo, ali pa s pogrezanjem elementa, dokler ne naletimo na manjši element, ali začetek tabele.
Zahtevnost
Časovna zahtevnost algoritma je v najslabšem in povprečnem primeru , v najboljšem (če je tabela že urejena) pa . Prostorska zahtevnost je , saj urejamo na mestu.
Psevdokoda for(i = 0; i < length(tabela)-1; i++) { j = i+1;
while ((j >= 1)&&(tabela[j] < tabela[j-1])) { zamenjaj(tabela[j], tabela[j-1]); j--;
Glej tudi
Shellovo urejanje - nadgradnja navadnih vstavljanj v več stopenj.
Kategorija:Algoritmi za urejanje podatkov Kategorija:Programiranje
no:Sorteringsalgoritme#Innstikksortering