Bubbelsortering

Bubbelsortering (engelska Bubble sort) är en enkel, dock inte särskilt effektiv, sorteringsalgoritm.

Algoritmen innebär att det område av en lista som skall sorteras gås igenom upprepade gånger och parvisa jämförelser görs av intilliggande element. Om elementen är i fel ordning kastas elementens ordning om. Efter varje genomgång av ett område kommer det sista talet att ha hamnat på rätt plats. Vid nästa genomgång reduceras därför det område som gås igenom med ett. Efter hand som sorteringen fortlöper kommer den korrekt sorterade delen i botten av listan att växa med ett element per genomgång av den ännu osorterade delen av listan och de ännu osorterade elementen "bubblar" uppåt, därav namnet på sorteringsalgoritmen.

Kod och pseudokod 
Med pseudokod kan algoritmen skrivas:
 procedure bubbleSort( A : lista av sorterbara objekt ) defined as:
   do
     swapped := false
     for each i in 0 to length( A ) - 2 do:
       if A[ i ] > A[ i + 1 ] then
         swap( A[ i ], A[ i + 1 ] )
         swapped := true
       end if
     end for
   while swapped
 end procedure
eller som
 
 procedure bubbleSort( A : lista av sorterbara objekt ) defined as:
   for each i in 1 to length(A) do:
      for each j in length(A) downto i + 1 do:
        if A[ j -1  ] > A[ j ] then
          swap( A[ j - 1],  A[ j ] )
        end if
      end for
   end for
 end procedure
Ett sätt att optimera algoritmen är att notera att efter varje slinga så kommer det största elementet att ligga på rätt plats så om listan innehåller n objekt så räcker det att gå igenom de n - 1 första elementen i andra slingan och så vidare och den modifierade algoritmen kan skrivas:
 procedure bubbleSort( A : lista av sorterbara objekt ) defined as:
   n := length( A )
   do
     swapped := false
     n := n - 1
     for each i in 0 to n do:
       if A[ i ] > A[ i + 1 ] then
         swap( A[ i ], A[ i + 1 ] )
         swapped := true
       end if
     end for
   while swapped
 end procedure

Här är ett exempel i programspråket Python:
def bubble_sort(A):
    # Tar en vektor A och sorterar den
    # returnerar sen den sorterade vektorn.
    n = len(A) - 1
    for j in range(n, 0, -1):
        for i in range(j):
            if A[i] > A[i+1]:
                A[i], A[i+1] = A[i+1], A[i]
            n = n - 1
    return A

Analys

Prestandan i bästa fall 
I bästa fall har Bubble sort komplexiteten O(n). När listan redan är sorterad kommer Bubble sort bara att gå igenom listan och sedan konstatera att inga element behöver byta plats. Detta innebär att Bubble sort bara behöver göra n - 1 jämförelser   för att konstatera att listan är helt sorterad. Den kommer även att använda betydligt mindre tid än O(n²), vilket är den teoretiskt sämsta tiden, om elementen i den osorterade listan inte ligger alltför långt ifrån sina riktiga platser.

Kaniner och sköldpaddor 
Elementens position spelar stor roll för bubblesorts prestanda. Stora element i början av listan utgör inga problem då de snabbt förflyttas bakåt. Små element i slutet av listan däremot flyttas mot listans början mycket långsamt, endast ett steg för varje gång listan gås igenom. Detta har lett till att man kallar dessa element kaniner och sköldpaddor (rabbits and turtles).

Olika försök har gjorts för att eliminera sköldpaddorna för att öka sorteringshastigheten. Cocktail sort har löst detta ganska bra, den har dock fortfarande O(n²) som sämsta fall. Comb sort jämför element på stora avstånd i listan och kan flytta sköldpaddor mycket snabbt innan den sorterar listan genom att jämföra element på kortare och kortare avstånd. Till slut avslutar comb sort med bubble sort. Comb sorts genomsnittliga hastighet är jämförbar med snabbare algoritmer som exempelvis Quicksort.

Exempel: Sortering av en lista med fyra siffror 

Ursprunglig lista: 2, 4, 1, 3
 Jämför 2 och 4 — Ordningen stämmer, inget platsbyte behövs. Listan nu: 2, 4, 1, 3
 Jämför nästa talpar, 4 och 1 — 1 ska vara först, byt plats på talen. Listan nu: 2, 1, 4, 3
 Jämför sista talparet, 4 och 3 — 3 ska vara först, byt plats på talen. Listan nu: 2, 1, 3, 4
Nu har listan gåtts igenom en gång. Sista talet ligger nu på rätt plats och nästa genomgång behöver vi därför inte ha med detta tal.
 Jämför 2 och 1 — 1 ska vara först, byt plats på talen. Listan nu: 1, 2, 3, 4
Vi ser nu att listan nu är rätt men ett datorprogram kan inte avgöra detta utan måste fortsätta tills hela sorteringen är klar.
 Jämför 2 och 3 — Ordningen stämmer, inget platsbyte behövs. Listan nu: 1, 2, 3, 4
Vi har nu gått igenom listan igen. Nu behöver vi bara jämföra första talparet.
 Jämför 1 och 2 — Ordningen stämmer, inget platsbyte behövs.
Sorteringen är nu klar. Resultat: 1, 2, 3, 4

Samma sortering fast presenterad i tabellform

Bubbel sort behöver O(n²) jämförelser för att sortera n objekt.

Externa länkar 
 Bubble sort i programkod i Wikibooks.
 Bubble sort code.

Sorteringsalgoritmer