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. ) algortitmer slik som seleksjonsortering eller bobblesortering
 Adaptiv sortering, dvs effektiv for datamengder som allerede er grunnleggende sortert: Tidskompleksiteten er  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 
 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

Kategori:Sorteringsalgoritmer