Inledning

Sortering av data är ett viktigt avsnitt inom datorvetenskap och programmering. Kunskap om sortering är viktig helt enkelt för att det gör dig till en bättre programmerare. Sortering av data är ofta en förutsättning för att senare effektivt kunna söka i datan.

Algoritmer är ett ord som beskriver en mängd instruktioner för att lösa en given uppgift. Inom programmering blir algoritmer avgränsad kod som beräknar ett resultat eller löser ett problem. En liknelse kan göras vid matlagning där ett recept kan motsvara en algoritm. De algoritmer vi skall titta på handlar om sortering av data eller mer specifikt av tal och siffror. Sorteringalgoritmer är oftast de första algoritmer som lärs ut då de löser ett enkelt problem och är tillräckligt avancerade för att erbjuda analyser och jämförelser. Märk väl att problemet är enkelt men lösningen däremot kan vara mer avancerad.

Förutsättningar

Det finns en uppsjö av olika sorteringsalgoritmer en del anpassade för att sortera siffror typ int eller double, andra för att sortera texter typ string. Datatypen som används avgör alltså vilka sorteringsalgoritmer som kan användas. De klassiska sorteringsalgoritmerna, och också flertalet av sorteringsalgoritmerna, sorterar tal. Algoritmerna vi skall undersöka kommer därför alla att utgå från följande problem:

Vi har en vektor på obestämd längd som innehåller olika tal. Vilka talen är vet vi inte på förhand därför kan inga antaganden göras på t.ex. minsta eller största förväntade värde på indatan. Ett exempel på indata skulle kunna vara:

• { 23, 14, 54, 2, 63, 22, 1, 3, 19, 32, 8 }

Resultatet efter sorteringsalgoritmen:

• { 1, 2, 3, 8, 14, 19, 22, 23, 32, 54, 63 }

Här följer en kort videopresentation av de olika sorteringsalgoritmer vi har valt ut. I filmerna använder vi spelkort (ess till knekt, ess är lägst) som representerar tal som skall sorteras. Filmklippen försöker i korta drag illustrera hur datorn sorterar tal med de olika algoritmerna. Det är lättare att förstå grundidén innan vi går in på detaljerna för varje algoritm.

Bubble sort

Bubble sort är kanske den enklaste algoritmen både att implementera och att förstå. Algoritmen jämför närliggande element i vektorn och byter plats på dem så att t.ex. högst värde flyttas framåt i vektorn. I videoexemplet ovan flyttas högst värde "framåt" (vänster i filmen). Efter första svepet genom vektorn så har det högsta värdet hittats och fått sin rätta plats. Algoritmen upprepar sedan samma procedur igen på de tal som är kvar.

Namnet "Bubble" kommmer från symboliken att tal "bubblar" upp ungefär som bubblor i kolsyrad läsk.

För mer information se artikeln Bubble Sort

Insertion sort

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.

För mer information se artikeln Insertion Sort

Quick sort

Quick sort börjar med att välja ett värde från vektorn. Detta värde brukar kallas pivot-värde. Pivot-värdet kan väljas slumpvis som i videoexemplet. Resterande värden jämförs sedan mot pivot-värdet och sorteras i två högar. En hög för mindre värden än pivot-värdet och en hög för större värden. När detta är gjort så har pivot-värdet hittat sin rätta plats i vektorn. Därefter upprepas sorteringen genom att välja ett nytt pivot-värde i någon hög av osorterade värden. På så vis delas vektorn ned i mindre och mindre delar.

För mer information se artikeln Quick Sort

Effektivitet

Algoritmer kan jämföras på olika sätt. De främsta egenskaperna som jämförs för att bedöma effektivitet är:

• Kortast tid. Hur lång tid tar algoritmen för att lösa problemet?
• Minst resurser. I programmering handlar det främst om hur mycket extra minne i form av variabler som behöver deklareras för att lösa problemet.
• Minst komplicerad. Oftast (men inte alltid) den mängd kod som går åt för att beskriva algoritmen.

Olika situationer kan avgöra vilka av de tre ovanstående egenskaperna som är viktigast. Generellt sett så kan vi nog säga att idag så är oftast den algoritm som gör jobbet snabbast den mest intressanta. Resurser i form av minne finns oftast i överflöd i dagens servrar och arbetsstationer. Implementationen är intressant för oss programmerare men inte ett dugg intressant för slutanvändaren av programmet/systemet.

Ordo-begreppet

Ordo (latin för ordning) är en matematisk term, O. Inom datorvetenskap brukar ordo användas för att jämföra effektivitet hos algoritmer. Ordo anger hur "tung" en fuktion är.

Datamängden betecknas n i beräkningar om effektivitet. Datamängden dvs. den mängd data in i en algoritm påverkar hur många beräkningar som behöver göras i algoritmen. I sorteringsalgoritmer är alltså datamängden hur många element i vektorn som skall sorteras.

Låt oss säga att vi kommer fram till att en algoritm har funktionen f(n)= 2n² + 3n + 20 beräkningar. Då bli O(f(n)) = O(n²). Ordo ger oss den funktion som växer snabbast med större värden på n. Konstanter och mindre termer faller bort då dessa har liten betydelse för stora värden på n.

Vi kan jämföra f(n) med g(n) = n³, dvs. O(g(n)) = O(n³) med olika värden för n.

Redan vid n = 10 ser vi att O(n³) > O(n²) och vid n = 1000 har vi en miljard beräkningar på g(n)!

Vid analys av en algoritms beräknkingsmängd så är det tre fall som är intressanta.

• Bästa fall ("best case"), alltså under optimala förutsättningar. I sorteringar kan det handla om att datamängden redan är sorterad när den skickas till sorteringsalgoritmen.
• Sämsta fall ("worst case"). T.ex. att datamängden är ordnad så att det krävs flest beräkningar.
• Medelfallet ("average case"). Kan beräknas genom att köra lagoritmen x antal gånger med slumpvis data för att bilda ett medelvärde.

En del algoritmer är så pass enkla att både bästa, sämsta och medelfallet är detsamma.

Exempel på analys

Vi skall nu analysera en algoritm som fösöker hitta största värdet i en vektor. Programmet ser ut som:

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

namespace ConsoleApplication1
{
    class Program
    {
		//Returnerar det största värdet i vektorn
		//
        static int Max(int[] vektor)
        {
            int largest = int.MinValue;
            for (int i = 0; i < vektor.Length; i++ )
            {
                if (vektor[i] > largest)
                    largest = vektor[i];
            }
            return largest;
        }

        static void Main(string[] args)
        {
            int[] tal = { 12, 4, 34, 21, 2, 64, 32, 56, 23, 11, 8 };
            int max = Max(tal);
            Console.WriteLine("Störst tal är: " + max);
        }
    }
}

Frågan är hur funktionen Max() beror på datamängden?

Vi har en loop som alltid går igenom alla tal i vektorn. Är det 10 tal i vektorn så görs det 10 jämförelser, är det 100 tal görs det 100 jämförelser. Alltså verkar vi ha en algoritm som är linjärt beroende av datamängden. Ordo är alltså O(n). Vi har heller inget sämsta eller värsta fall. Alla fall har O(n).

Resurserna som krävs för att utföra algoritmen är endast en extra variabel, largest. Detta kan då anges som O(1) i extra minnesanvändning.

Om vi återgår till begreppet effektivitet (kortast tid, minst resurser, minst komplicerad) så anges ibland endast tiden som ett mått på effektivitet. I detta exempel alltså O(n). Vi kan också ange minnesanvändning som O(1) och subjektivt ange komplexiteten som enkel.

Vad händer om vi modifierar algoritmen en aning och inför ett villkor på loop'en?

        static int Max(int[] vektor)
        {
            int largest = int.MinValue;
            for (int i = 0; i < vektor.Length && largest != int.MaxValue; i++ )
            {
                if (vektor[i] > largest)
                    largest = vektor[i];
            }
            return largest;
        }

Har largest fått maxvärdet för typen int så kommer vi inte att hitta något större värde. Vad har ändrats nu? Vad är det bästa fallet för algoritmen nu?

Skickar vi nu in en datamängd där det första värdet i listan är maxvärdet för int så kommer algoritmen att avslutas och returnera det. Alltså har vi nu ett bästa fall på O(1). Sämsta fall är då ett maxvärde ej finns i vektorn, då fungerar algoritmen precis som innan.