Bubbelsortering

Från Wikipedia
Hoppa till: navigering, sök

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örelser av intilliggande element.

När två intilliggande 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.

Exempel på bubbelsortering.

Kod och pseudokod[redigera | redigera wikitext]

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[redigera | redigera wikitext]

Best-case performance[redigera | redigera wikitext]

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-1 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[redigera | redigera wikitext]

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. 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 4 siffror[redigera | redigera wikitext]

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.

Se även på Wikisource[redigera | redigera wikitext]