Innstikksortering

Innstikksortering er en enkel sorteringsalgoritme som bygger opp en sortert tabell (eller liste) et element av gangen. Algoritmen 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, og en femlinjers optimalisert versjonen^[1]
Effektiv på svært små datamengder, liksom andre kvadratiske sorteringsalgoritmer
Mer effektiv i praksis på de fleste andre enkle kvadratiske (dvs. $O (n 2)$ ) algortitmer slik som seleksjonsortering eller bobblesortering
Adaptiv sortering, dvs effektiv for datamengder som allerede er grunnleggende sortert: Tidskompleksiteten er $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 kortspillet Bridge, bruker de vanligvis en metode som ligner på innstikksortering.^[2]

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å:

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]);
        }

Referanser

^ Bentley, Jon (2000). Programming Pearls. ACM Press/Addison–Wesley.
^ Sedgewick, Robert (1983), Algorithms, Addison-Wesley, ss. 95ff, ISBN 978-0-201-06672-2 .

Denne artikkelen er en spire. Du kan hjelpe Wikipedia ved å utvide den.

Autoritetsdata

[pearls-1] Bentley, Jon (2000). Programming Pearls. ACM Press/Addison–Wesley.

[2] Sedgewick, Robert (1983), Algorithms, Addison-Wesley, ss. 95ff, ISBN 978-0-201-06672-2 .

[1]

[2]