Algoritem za navadno vstavljanje
Iz E-študij, proste zakladnice študentskega znanja
Algoritem za navadno vstavljanje (Insertion Sort) je sortirni algoritem.
Deluje tako, da razširja skupino urejenih elementov z začetka in dodaja prvi naslednji (še neurejeni) element desno od skupine urejenih elementov tako, da ga prekopira na začasno mesto, vse večje od njega v urejeni skupini premakne za eno mesto naprej, ko pa naleti na manjši element, element iz začasnega mesta vstavi v nastalo "luknjo" zaradi premikanja večjih elementov.
Obstajajo izjeme:
- Če večjih elementov ni se skupina enostavno razširi, tako da zajema novi element (ker je največji).
- Če so vsi elementi večji in pride do začetka seznama, element vstavi na začetek (ker je najmanjši).
- Ko sreča enak element ga ne premika ampak element iz začasnega mesta vstavi v že obstoječo luknjo (s tem se izognemo nepotrebnemu premiku).
Vsebina |
Algoritem
for (int i=1; i<a.length;++i)
{
x=a[i];
vstavi x na pravo mesto med elemente od a[0] do a[i];
}
Opis
Imamo tabelo vhodnih elementov, ki jih moramo urediti. Torej moramo to tabelo urediti. To pa, zelo poenostavljeno rečeno, delamo takole: najprej vzameno prvi element tabele in ga proglasimo za urejenega, nato pa vzameno naslednega in ga primerjamo z urejenim delom in sicer tako da gledamo z desne proti levi kateri elementi so večji od našega elementa ne večji ali enaki in se premikamo levo po urejenem delu tabele. Naš element vstavimo za manjši ali enak element. Če pridemo do konca ga pač na koncu dela ustavimo, ker to pomeni, da ni manjšega elementa, kot je naš trenutni v urejenem delu. Torej delamo od desne proti levem delu urejenega dela
Algoritem v Javi
public class SortiranjeObjektov { public static void straightinsertion(Element[] a) { int i,j; Element x; for (i=1; i<a.length; ++i) { x=a[i]; for (j=i-1; (j>=0 && (x.manjsi(a[j]))); --j) a[j+1]=a[j]; a[j+1]=x; } } }
Analiza kompleksnosti
Pomembni so:
- premiki
- primerjave
Število primerjanj
Število primerjanj je odvisno od tega kolikokrat se notranja zanka izvede.
Odvisna je od števila i.
- v i-tem koraku
-
(najboljši primer)
-
(najslabši primer)
-
(povprečno)
- v celoti
-
(najboljši primer)
-
(najslabši primer)
-
(povprečno)
Število premikov
- v i-tem koraku
-
(najboljši primer)
-
(najslabši primer)
-
(povprečno)
- v celoti
-
(najboljši primer)
-
(najslabši primer)
-
(povprečno)
- štejemo samo primerjave, ki jih porabimo preden element vstavimo na pravo mesto
O(n^2)
Postopek po korakih
- vzamemo opazovan element (naslednji od tistega, ki smo ga nazadnje obdelali) in ga vstavimo na primerno mesto na levi; števila, ki so desno od tega stevila pustimo pri miru.
- dveh enakih števil ne menjamo!
Primer
8 7 3 5 0 4 2 1 3 0 8|7 3 5 0 4 2 1 3 0 7 8|3 5 0 4 2 1 3 0 3 7 8|5 0 4 2 1 3 0 3 5 7 8|0 4 2 1 3 0 0 3 5 7 8|4 2 1 3 0 0 3 4 5 7 8|2 1 3 0 0 2 3 4 5 7 8|1 3 0 0 1 2 3 4 5 7 8|3 0 0 1 2 3 3 4 5 7 8|0 0 0 1 2 3 3 4 5 7 8
