Urejanje z navadnim vstavljanjem

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Urejanje z navadnim vstavljanjem
Insertion sort animation.gif
Grafični prikaz algoritma navadnih vstavljanj
Osnovni podatki
Vrsta: algoritem za urejanje podatkov
Podatkovna struktura: tabela
Časovna zahtevnost
Zgornja meja zahtevnosti: O(n2)
Spodnja meja zahtevnosti: O(n)
Pričakovana zahtevnost: O(n2)
Prostorska zahtevnost
Prostorska zahtevnost: O(1)


Urejanje z navadnim vstavljanjem (angleško Insertion sort) 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[uredi | uredi kodo]

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[uredi | uredi kodo]

Č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[uredi | uredi kodo]

  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[uredi | uredi kodo]