Bookmark and Share

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

Sorteringsalgoritmer

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:

Resultatet efter sorteringsalgoritmen:

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

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.

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

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.

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

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.

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:

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)= 2n2 + 3n + 20 beräkningar. Då bli O(f(n)) = O(n2). 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) = n3, dvs. O(g(n)) = O(n3) med olika värden för n.

n f(n) g(n)
1 25 1
10 250 1000
100 20320 1000000
1000 2003020 1000000000

Redan vid n = 10 ser vi att O(n3) > O(n2) 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.

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:

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?

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.

Viktiga begrepp

  • Algoritmer
  • Bubble sort
  • Insertion sort
  • Quick sort
  • pivot
  • Ordo

Kommentarer

2 inlägg