Bookmark and Share

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

Bubble Sort

Inledning

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.

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.

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

Implementation

Bubble sort räknas som den lättaste sorteringsalgoritmen att implementera. Med hjälp av videon kan du lättare förstå koden som presenteras här, vi ska ändå försöka att beskriva den i ord.

Tanken att flytta det största talet framför sig kan omsättas till kod med en for-loop. När detta är gjort en gång så kommer vi att ha det högsta talet i slutet av vektorn. Det vi behöver är att upprepa samma loop igen och igen tills dess att vi flyttat alla tal i ordning. Det kommer därför att krävas en yttre loop som snurrar en gång för varje tal som skall sorteras.

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.

Analys

Bästa fall

Det bästa fallet inträffar då datan som skall sorteras redan är sorterad. Variabeln needsSorting i vår implementation håller koll på om några tal bytt plats när den inre loop'en kört. Om inget tal har bytt plats betyder då att alla tal redan är sorterade och algoritmen avbryts.

Det krävs alltså att den inre loop'en måste köras minst en gång. Eftersom den 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.

Bubble 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å Bubble 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. Sätt gärna en break point i algoritmen och stega igenom den när du skickar in t.ex. data med längd 10. Du kommer då att märka att den inre loop'en körs först 9 gånger, sedan 8, sedan 7, osv. Matematiskt skulle vi sätta upp det som n-1, n-2, n-3...0 alltså en typisk aritmetisk summa. Antalet upprepningar blir (n)*(n-1)/2.

Detta ger O(n2). Första mätningen på 1000 tal kan vi bortse ifrån då den tog 5 ms och precisionen i mätningen är dålig. Skillnaden mellan 10000 tal, vilket tog 0,26s och 100000 tal som tog 25,4s ä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).

Bubble Sort är inte känd för att vara effektiv. Det enda som är bra med Bubble Sort är att algoritmen har ett bra namn! 25 sekunder för att sortera en relativt liten mängd data är inte okej!

En algoritm men O(n2) kan t.o.m. bli en säkerhetsbrist. Vi tänker oss att vi implementera en Bubble Sort i ett webbsystem. Skulle nu datan som algoritmen sorterar kunna påverkas att bli större så skulle ett fåtal anrop till webbservern resultera att servern blir upptagen att sortera tal i kanske flera minuter framöver...

Viktiga begrepp

  • Bubble sort

Kommentarer

1 inlägg