Bookmark and Share

Svårighetsgrad
Svårighetsgrad
Betyg (6 röster)
BetygBetygBetygBetygBetyg
 

Insertion Sort

Inledning

Insertion sort räknas också som en relativt enkel algoritm. Algoritmen börjar med de två första talen och sorterar dem om så behövs. Därefter sorteras varje nytt tal "bakåt" (höger i filmen) i vektorn med tal för att finna rätt plats. De tal som redan är undersökta kan anses som sorterade, dvs. början av vektorn är sorterad.

Filmklippen som presenteras här kräver en nyare version av Adobe Flash Player. Du behöver även ha javaScript aktiverat i din webbläsare. Behöver du Flash Player så kan du ladda hem den här: Adobe Flash player.

Implementation

Insertion sort är ungefär lika svår att begripa som Bubble Sort. Tanken är att algoritmen skapar en "svans" efter sig allteftersom tal sorteras "bakåt" i vektorn. När varje nytt tal börjar sorteras, dvs. när ytterloop'en börjar om, så är talen i "svansen" inbördes sorterade.

Metoden nedan är deklarerad static då exemplet är taget från ett Console Application

Prestanda

För att mäta prestandan på algoritmen så har vi konstruerat ett Console Application som slumpar fram 1000, 10000 och sist 100000 heltal. Talen skickas först osorterade till algoritmen för att mäta generell prestanda. Därefter skickas den sorterade datan en gång till genom algoritmen för att mäta prestandan under andra förutsättningar.

Testerna som gjorts har körts på en något äldre maskin så bli inte förvånad om du får mycket bättre tider vid en jämförelse.

Testprogram

Resultat

bild

Då testprogrammet använder DateTime för att mäta tiden blir resultatet av tider under 5 ms opålitliga. Alla resultat < 5 ms får anses som snabba.

Vi kommer att göra en del jämförelser med resultat från artikeln om Bubble Sort.

Analys

Bästa fall

Det bästa fallet inträffar då datan som skall sorteras redan är sorterad. Den inre loop'en som jämför tal "bakåt" i vektorn kommer i detta fall inte att behöva jobba särskilt mycket. Det räcker med en "titt bakåt" för varje tal som skall sorteras för att upptäcka att talet redan ligger på rätt plats.

Det krävs alltså att den yttre loop'en måste köras minst en gång och att den inre loop'en blir avbryten varje gång. Eftersom den yttre loop'en bygger på längden av datan så kan vi beskriva bästa fallet som O(n), där n betecknar datamängden. Rent tidsmässigt kan vi se i bilden ovan att alla fall där redan sorterad data skall sorteras avverkas snabbt.

O(n) i bästa fall är samma grad av prestanda som Bubble Sort har.

Insertion sort har, när bästa fallet inte inträffar, samma prestanda för medelfallet och sämsta fallet.

Medelfall och sämsta fall

Då Insertion Sort använder dubbla loop'ar för att sortera tal så får vi en beräkningsmängd som ökar kvadratiskt med datamängden. Även om den inre loop'en beror på hur datan slumpar sig så borde varje tal som sorteras i snitt sorteras bakåt hälften av vad "svansen" (de redan sorterade talen) är lång. Detta ger direkt en faktor 2 i förbättring jämfört med t.ex. Bubble Sort.

Prestandan blir, precis som Bubble Sort, O(n2). Första mätningen på 1000 tal kan vi bortse ifrån då den tog 3 ms och precisionen i mätningen är dålig. Skillnaden mellan 10000 tal, vilket tog 65 ms och 100000 tal som tog 6354 ms (6,4 s) är mer intressant. Datamängden från 10000 till 100000 ökar med en faktor 10. Tiden algoritmen tar för att sortera ökar med en faktor 100! dvs. 10*10 eftersom effektiviteten är O(n2).

6,4 s för att sortera lite data är fortfarande rysligt dåligt. Bubble Sort hade å andra sidan ett resultat som var ca 4 gånger värre jämt över! Det tar 6,4 s för Insertion Sort att göra det som tog 25 s för Bubble Sort.

Jämförelser med andra algoritmer

Slumpad data 1000 10000 100000
Bubble Sort 0 259 25440
Insertion Sort 0 64 6354
Sorterad data 1000 10000 100000
Bubble Sort 0 0 0
Insertion Sort 0 0 0

Tid är angiven i millisekunder (1s = 1000ms). Ett resultat på 0 indikerar inte att tiden verkligen var 0 ms utan snarare att det gick för snabbt för att mätas med vår metod.

Viktiga begrepp

  • Insertion sort

Kommentarer

1 inlägg