Urejanje z vstavljanjem/Navadno vstavljanje

Iz MaFiRaWiki

Vsebina


Navadno vstavljanje ali insertion sort je enostavna metoda za urejanje manjšega števila podatkov v tabeli, ko enostavnost kode prevlada nad slabšo učinkovitostjo. Časovna zahtevnost metode je O(n2). Navadno vstavljanje je osnova metod hitro urejanje (Quicksort) in urejanje z vstavljanjem s padajočim prirastkom (Shellsort).

Tabela podatkov je v vsakem trenutku razdeljena na dva dela: prvi del je urejen, drugi del je neurejen. Na začetku urejeni del predstavlja prvi element tabele, ostali so neurejeni. Elemente iz neurejenega dela po vrsti vstavljamo na pravo mesto v urejeni del tako, da zaporedoma primerjamo element, ki ga vstavljamo, z elementom v urejenem delu in ju menjamo, če je novi element manjši. Končamo, ko v neurejenem delu ni več elementov.

Opis algoritma

  • Spremenljivki i priredi 1.
  • i - ti (trenutni) element po vrsti primerjaj z elementi pred njim; začni z elementom na mestu i - 1. Dokler je trenutni element manjši od primerjanega ali dokler nisi na začetku, primerjani element prestavi za eno mesto naprej.
  • i - ti element vsatvi na svoje mesto.
  • i povečaj za 1.
  • Korake razen prvega ponavljaj, dokler i ne preseže števila elementov.

Algoritem

Pomen spremenljivk:

  • n ...... število elementov v tabeli
  • a[i] ... element v tabeli a, kjer je 0<=i<=n
  • a[j] ... element iz tabele, s katerim primerjamo trenutni element
  • j ...... pomožni števec
for i = 1 to n 
 trenutni=a[i] 
 j=i-1 
  while(j>=0) and (a[j]>trenutni) do 
   a[j+1]=a[j] 
   j=j-1 
  end_while 
 a[j+1]=trenutni
end_for

Primer

Podano tabelo uredimo z navadnim vstavljanjem.

44 55 12 42 94 18 6 67

  1. Korak, i = 1:
    Primerjamo drugi element tabele z indeksom 1 s prvim elementom v tabeli. Ker je 55 > 44 elementa ostaneta na svojih mestih. Naredili nismo nobene menjave.
    44 55 12 42 94 18 6 67
  2. Korak, i = 2:
    Primerjamo tretji element tabele z indeksom 2 z drugim elementom v tabeli. Ker je 12 < 55 elementa zamenjamo, primerjamo še s prvim, ker je 12 < 44, ju tudi zamenjamo. Naredimo 2 menjavi. Dobimo:
    12 44 55 42 94 18 6 67
  3. Korak, i = 3:
    Primerjamo četrti element tabele z indeksom 3 s tretjim elementom v tabeli. Ker je 42 < 55, ju zamenjamo, primerjamo trenutni element đe z drugim in ker je 42 < 44, ju zamenjamo. Naredimo 2 menjavi. Dobimo:
    12 42 44 55 94 18 6 67
  4. Korak, i =4:
    Primerjamo peti element tabele z indeksom 4 s tretjim elementom v tabeli. Ker je 94 > 55 elementa ostaneta na svojih mestih. Naredili nismo nobene menjave.
    12 42 44 55 94 18 6 67
  5. Korak, i = 5:
    Primerjamo šesti element tabele z indeksom 5 s petim elementom v tabeli. Ker je 18 < 94, ju zamenjamo, primerjamo s 55, ker je 18 manjše, ju zamenjamo ... tako vse do 12. Naredimo 4 menjave, 18 smo pripeljali na drugo mesto v tabeli. Dobimo:
    12 18 42 44 55 94 6 67
  6. Korak, i = 6:
    Primerjamo sedmi element tabele z indeksom 6 s šestim elementom v tabeli. Ker je 6 manjša od vseh elementov pred njo, jo postopoma pomikamo čisto na začetek. Opravimo 6 menjav. Dobimo tabelo:
    6 12 18 42 44 55 94 67
  7. Korak, i = 7:
    Primerjamo zadnji element tabele z indeksom 7 s šestim elementom v tabeli. Ker je 67 < 94, ju zamenjamo. Naredimo 1 menjavo. Dobimo urejeno tabelo:
    6 12 18 42 44 55 67 94

Implementacija

Glej tudi

Viri in literatura

Osebna orodja