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
• Effektiv på svært små datamengder, liksom andre kvadratiske sorteringsalgoritmer
• Mer effektiv i praksis på de fleste andre enkle kvadratiske (dvs. O(n²)) 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.

Fremgangsmåte

1. 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.
2. Man går bakover i listen igjen og flytter alle elementene 1 indeks opp i listen.
3. 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