Bubbelsortering

Bubbelsortering

Klass	Sorteringsalgoritm
Datastruktur	array
Tidskomplexitet värsta fall	O(n2)
Tidskomplexitet bästa fall	O(n)
Tidskomplexitet genomsnitt	O(n2)
Minneskomplexitet värsta fall	O(n)

Bubbelsortering redigerad färg.

Exempel på 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

Första jämförelseserien
2	4	1	3	Rätt ordning, inget platsbyte
2	4	1	3	Fel ordning, byt plats
2	1	4	3	Fel ordning, byt plats
Andra jämförelseserien
2	1	3	4	Fel ordning, byt plats
1	2	3	4	Rätt ordning, inget platsbyte
Tredje jämförelseserien
1	2	3	4	Rätt ordning, inget platsbyte

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.