Redigerer Innstikksortering

'''Innstikksortering''' er en enkel [[sorteringsalgoritme]] som bygger opp en [[sortert tabell]] (eller liste) et element av gangen. [[Algoritme]]n er mye mindre effektiv på store lister enn [[quicksort]], [[haugsortering]] eller [[flettesortering]]. Innsettingsortering har likevel flere fordeler:

* Enkel implementasjon: [[Jon Bentley]] viser en trelinjers versjon i [[C (programmeringsspråk)|C]], og en femlinjers [[Programvareoptimalisering|optimalisert]] versjonen<ref name="pearls">{{cite book |first=Jon |last=Bentley |title=Programming Pearls |year=2000 |publisher=ACM Press/Addison–Wesley}}</ref>
* Effektiv på svært små datamengder, liksom andre kvadratiske sorteringsalgoritmer
* Mer effektiv i praksis på de fleste andre enkle kvadratiske (dvs. {{math|''O''(''n''<sup>2</sup>)}}) algortitmer slik som [[seleksjonsortering]] eller [[bobblesortering]]
* [[Adaptiv sortering]], dvs effektiv for datamengder som allerede er grunnleggende sortert: [[Tidskompleksitet]]en er {{math|O(''nk'')}} når hvert element som innmates ikke er mer enn k plasser unna sin sorterte posisjon
* Stabil: Forandrer ikke den relative rekkefølge av elementer med like nøkler
* [[På-stedet algoritme]]: Krever bare en konstant mengde O(1) med tilleggsminne
* [[Online algoritme]]: Kan sortere lister etterhvert som den mottar dem

Når folk sorterer kort manuelt under [[kortspill]]et [[Bridge]], bruker de vanligvis en metode som ligner på innstikksortering.<ref>{{Citation |last=Sedgewick |first=Robert |author-link=Robert Sedgewick (computer scientist) | title = Algorithms |year=1983 |publisher=Addison-Wesley |isbn=978-0-201-06672-2 | pages = 95ff}}.</ref>

=== Fremgangsmåte ===
# Man finner et element i en liste hvor det neste elementet er mindre enn det man ser på i øyeblikket og tar det minste ut av listen.
# Man går bakover i listen igjen og flytter alle elementene 1 indeks opp i listen.
# Når man kommer til indeksen hvor indeks+1>tallet man tok ut og indeks-1<tallet man tok ut så setter man tallet inn på indeksen.

Eksempel på en løsning i java som sorterer elementene i listen a og printer de ut etterpå:<syntaxhighlight lang="java" line="1">
int[] a = {5,1,2,34,8,21,31,4124,0};
        int til = a.length-1;
        for(int fra = 0; fra<til; fra++){
            if(a[fra]>a[fra+1]){
                int tmp = a[fra+1];
                int i = fra;

                while(i >= 0 && a[i]>tmp){
                    a[i+1] = a[i];
                    i--;
                }
                a[i+1] = tmp;
            }
        }
        for(int f = 0; f<a.length;f++){
            System.out.println(a[f]);
        }
</syntaxhighlight>

==Referanser==
<references/>

{{spire}}
{{Autoritetsdata}}

[[Kategori:Sorteringsalgoritmer]]