Bubbelsortering

Från Rilpedia

Texten från svenska Wikipedia

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

Metoden går ut på att man upprepade gånger går igenom det område i listan som ska sorteras och gör parvis jämförselser av intilligande element.

När två intilligande element ligger i fel ordning byter man plats på dem. Varje gång man gått igenom ett område kommer det sista talet att ha hamnat på rätt plats. Nästa gång reducerar man därför det område man går igenom med ett. Efter hand som man gör sorteringen kommer listan i botten bli alltmer korrekt och de överblivna talen "bubblar" uppåt, därav namnet på sorteringsalgoritmen.

Kod och pseudokod

Om algoritmen skrivs med pseudokod kan den uttryckas:

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

Den kan även uttryckas 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 osv. och då kan algoritmen uttryckas som nedan:

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 konkret exempel i 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

Best-case performance

I bästa fall har bubble sort en komplexitet O(n). När listan redan är sorterad kommer bubblesort bara gå igenom listan och sen konstatera att inga element behöver byta plats. Vilket leder till att bubblesort bara behöver göra n jämförelser för att konstatera att en lista är helt sorterad. Den kommer även att använda betydligt mindre tid än O(n²), vilket är den teoretiskt värsta tiden, om elementen i den osorterade listan inte ligger allt fö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 början väldigt 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 värst. Comb sort jämför element på stora avstånd i listan och kan flytta sköldpaddor väldigt snabbt innan den sorterar listan genom att jämföra element på kortare och kortare avstånd. Tillslut 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 4 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.

Se även på Wikisource

• Bubble sort i programkod
• Bubble sort code