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.

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

static void BubbleSort(int[] data)
{
	bool needsSorting = true;
	//Gör en loop för varje tal som skall sorteras, avbryt om talen är sorterade
	for (int i = 0; i < data.Length - 1 && needsSorting; i++)
	{
		//Signalera att vi börjar om en ny vända med sortering
		needsSorting = false;
		//Gå igenom alla tal fram till och med de tal som ev. 
		//redan är sorterade (variabeln i)
		for (int j = 0; j < data.Length - 1 - i; j++)
		{
			//Flytta större tal fram i vektorn
			if (data[j] > data[j + 1])
			{
				//Signalera att vi kommer att behöva fortsätta sortera
				needsSorting = true;
				//Byt plats på tal
				int tmp = data[j +1];
				data[j + 1] = data[j];
				data[j] = tmp;
			}
		}
		//Har vi nu inte behövt sortera några tal så är 
		//needsSorting == false och loop'en kommer att avbrytas
	}
}

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 BubbleSort
{
    class Program
    {
        static void BubbleSort(int[] data)
        {
            bool needsSorting = true;
            //Gör en loop för varje tal som skall sorteras, avbryt om talen är sorterade
            for (int i = 0; i < data.Length - 1 && needsSorting; i++)
            {
                //Signalera att vi börjar om en ny vända med sortering
                needsSorting = false;
                //Gå igenom alla tal fram till och med de tal som ev. 
                //redan är sorterade (variabeln i)
                for (int j = 0; j < data.Length - 1 - i; j++)
                {
                    //Flytta större tal fram i vektorn
                    if (data[j] > data[j + 1])
                    {
                        //Signalera att vi kommer att behöva fortsätta sortera
                        needsSorting = true;
                        //Byt plats på tal
                        int tmp = data[j +1];
                        data[j + 1] = data[j];
                        data[j] = tmp;
                    }
                }
                //Har vi nu inte behövt sortera några tal så är 
                //needsSorting == false och loop'en kommer att avbrytas
            }
        }

        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;
                BubbleSort(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;
                BubbleSort(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.

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

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