Indsættelsessortering
Fra Wikipedia, den frie encyklopædi
Indsættelsessortering er en effektiv algoritme for sortering af få elementer. Algoritmen sammenlignes tit med hvordan de fleste mennesker sorter et hånd spillekort. Vi starter med en tom venstrehånd og trækker et kort ad gangen fra en bunke kort og indsætter kortet i den rigtige position i venstrehånden. Når vi skal afgøre, hvor kortet skal indsættes, sammenligner vi det med korterne, der allerede findes i hånden, fra højre mod venstre. Både undervejs og i slutningen af algoritmen vil korterne i venstrehånden altid være korrekt sorteret.
[redigér] Algoritmen
Indsættelsessorteringsalgoritmen illustreres ved et eksempel. På figuren nedenfor svarer de grå felter til de kort, som er i venstrehånden, og de røde felter svarer til de kort, der skal sorteres. Vi antager, at det første kort er allerede sorteret (da der ikke er andre at sammenligne med.) Derfor begynder algoritmen med at sortere kort nr. 2, som vist på figur (a). Undervejs i algoritmen er listen bestående af de grå felter hele tiden sorteret, figur (b) – (e). På den sidste figur er listen færdigsorteret, figur (f).
[redigér] Beregningskompleksiteten
Algoritmens tidskompleksitet er i værste tilfælde Θ(n2), hvilket forekommer i præcis det tilfælde, hvor listen er sorteret i omvendt rækkefølge fra starten af. Da skal hvert element sammenlignes med alle de andre elementer i listen, når det skal sorteres.
