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.

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

static void InsertionSort(int[] data)
{
	//Gör en loop för varje tal som skall sorteras 
	//börja på index 1 då vi kommer att titta "bakåt" i vektorn
	for (int i = 1; i < data.Length; i++)
	{
		//Stega bakåt från position i ned till 1 om så behövs
		for (int j = i; j > 0; j--)
		{
			//jämför med talet "bakom" och se om det är större
			if (data[j] < data[j - 1])
			{
				//byt plats på tal
				int tmp = data[j - 1];
				data[j - 1] = data[j];
				data[j] = tmp;
			}
			//annars avsluta innerloop'en 
			else
				break;
		}
	}
}

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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace InsertionSort
{
    class Program
    {
        static void InsertionSort(int[] data)
        {
            //Gör en loop för varje tal som skall sorteras 
            //börja på index 1 då vi kommer att titta "bakåt" i vektorn
            for (int i = 1; i < data.Length; i++)
            {
                //Stega bakåt från position i ned till 1 om så behövs
                for (int j = i; j > 0; j--)
                {
                    //jämför med talet "bakom" och se om det är större
                    if (data[j] < data[j - 1])
                    {
                        //byt plats på tal
                        int tmp = data[j - 1];
                        data[j - 1] = data[j];
                        data[j] = tmp;
                    }
                    //annars avsluta innerloop'en 
                    else
                        break;
                }
            }
        }

        static int[] GenerateData(int size)
        {
            Random rnd = new Random();
            int[] data = new int[size];

            for (int i = 0; i < data.Length; i++)
                data[i] = rnd.Next(data.Length);

            return data;
        }

        static void Main(string[] args)
        {
            int[] sizes = new int[] { 1000 , 10000, 100000 };

            for (int i = 0; i < sizes.Length; i++)
            {
                Console.WriteLine("Skapar slumpad data av längd " + sizes[i]);
                int[] data = GenerateData(sizes[i]);

                Console.WriteLine("Sorterar slumpad data");
                DateTime startTid = DateTime.Now;
                InsertionSort(data);
                TimeSpan deltaTid = DateTime.Now - startTid;
                Console.WriteLine("Det tog {0:0.00} ms att sortera.\n", deltaTid.TotalMilliseconds);

                Console.WriteLine("Sorterar redan sorterad data");
                startTid = DateTime.Now;
                InsertionSort(data);
                deltaTid = DateTime.Now - startTid;
                Console.WriteLine("Det tog {0:0.00} ms att sortera.\n", deltaTid.TotalMilliseconds);
            }

        }
    }
}

Resultat

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 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(n²). 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(n²).

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

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.