Hoppa till innehållet
Hem

Bubblessortering (bubble sort) – grundläggande algoritm och egenskaper

Bubblessortering är en enkel jämförelsebaserad sorteringsalgoritm, lätt att förstå och implementera. Artikeln förklarar princip, varianter, egenskaper, användningsområden och jämförelser med andra algoritmer.

Författare: Skapad: Uppdaterad:

Översikt

Bubblessortering, ofta kallad bubble sort på engelska, är en av de enklaste sorteringsalgoritmerna. Den bygger på att jämföra intilliggande element i en lista och byta plats när de står i fel ordning, tills hela listan är sorterad. Namnet syftar på hur mindre element "bubblar" mot början eller slutet av listan beroende på implementationen.

Bildgalleri

2 Bilder
Bubble-sort-example-300px
simple.wikipedia.org · CC BY-SA 3.0

Hur det fungerar

Algoritmen går igenom listan i flera omgångar (pass). I varje pass jämförs par av intilliggande element; om de är i fel ordning byts deras platser. Efter ett pass ligger åtminstone ett element på sin slutgiltiga position. Genom att upprepa processen minskar antalet osorterade element tills inga byten behövs.

Egenskaper och varianter

  • Stabil: bevarar ordningen mellan likvärdiga element.
  • I plats (in-place): kräver konstant extra minne.
  • Tidskomplexitet: i allmänhet O(n²) i medel- och värsta fall, men med en tidig avbrottskontroll kan bästa fall bli O(n) för redan sorterade listor.
  • Varianter: optimerad bubblessortering som använder en flagga för att upptäcka att inga byten skedde, och "cocktail shaker" (bidirektionell bubbel) som växlar riktning mellan pass.

Historia och användning

Bubblessortering har länge använts i undervisning tack vare sin enkelhet och lätta visualisering: stegvisa byten gör det tydligt hur sortering går till. I praktiska system ersätts den ofta av snabbare algoritmer för stora dataset, men den kan vara acceptabel för mycket små listor eller där kodens läsbarhet prioriteras framför prestanda.

Jämförelser och notabla fakta

Jämfört med andra enkla n²-algoritmer som urvalssortering (selection sort) och insättningssortering (insertion sort) är bubblessortering ofta långsammare i praktiken men mer intuitiv att förklara. Insertion sort är till exempel ofta bättre för nästan sorterade listor utan extra optimering. Bubblessortering används även som pedagogiskt exempel i algoritmvisualiseringar och som bas för att förstå komplexitetsbegreppet. För vidare läsning om algoritmen och dess varianter, se mer detaljerad beskrivning och illustrativa animationer via relaterade resurser.

En bubbel sort illustrerad  
En bubbel sort illustrerad  

Algoritm

Algoritmen jämför par av element i en lista. De element som utgör paren ligger bredvid varandra. De två elementen i varje par jämförs med varandra i tur och ordning, med början i listans ena ände. Det innebär till exempel att det första och andra elementet jämförs, därefter det andra och tredje elementet, därefter det tredje och fjärde och så vidare. Om elementen i det aktuella paret inte är i rätt ordning byter de två elementen plats. Denna process - att jämföra två element - görs om och om igen tills hela listan är sorterad. Listan är sorterad när det inte finns några fler par som måste bytas.

I bästa fall, när listan redan var sorterad innan algoritmen kördes, är algoritmens komplexitet O(n) (Big O-notation). I det värsta fallet, där listan börjar med att vara sorterad i omvänd ordning, O(n²).

 
Ett exempel på en bubbla. Jämför nästa par från början av listan. Byt ut deras positioner om de inte är i rätt ordning (den andra i paret är mindre än den första i paret). Efter varje iteration behöver ett mindre element (det sista) jämföras tills det inte finns några fler element kvar att jämföra.  
Ett exempel på en bubbla. Jämför nästa par från början av listan. Byt ut deras positioner om de inte är i rätt ordning (den andra i paret är mindre än den första i paret). Efter varje iteration behöver ett mindre element (det sista) jämföras tills det inte finns några fler element kvar att jämföra.  

Genomförande

I ett imperativt programmeringsspråk kan bubbelsortering implementeras genom att använda en flaggvariabel och genomgå arrayens element i en loop:

  1. Ställ in flaggan sorterad.
  2. Börja i ena änden och betrakta varje angränsande par av element i en vektor efter varandra (i deras ordning).
  3. Om ett pars element är oordnade byter du dem och rensar flaggan.
  4. Upprepa de föregående stegen tills sorteringen fortfarande är inställd.

Alternativt, eftersom det största värdet stiger till det högsta indexet i den första iterationen och sedan har nått sin slutliga högra position, sorterar två for-slingor som är inbäddade i varandra också vektorn:

for top ≔ high(vector)-1 downto low(vector) do for current ≔ low(vector) to top do if vector[current] > vector[current+1] then exchange(vector, current, current+1)
 

Relaterade sidor

  • Sortering genom inskjutning
  • Urvalssortering
 

Frågor och svar

F: Vad är bubbelsortering?

S: Bubble sort är en enkel sorteringsalgoritm.

F: Varför får nya studenter oftast lära sig bubblesortering?

S: Bubblesortering är enkel att förstå, så den lärs vanligtvis ut till nya studenter.

F: Hur effektiv är bubblesortering jämfört med andra sorteringsalgoritmer?

S: Bubble sort är inte lika effektiv som vissa andra sorteringsalgoritmer.

F: Varför kallas bubblesortering för bubblesortering?

S: Namnet kommer från det faktum att varje objekt i listan "bubblar" upp dit det ska, som bubblor i vatten.

F: Är bubbelsortering lämplig för stora datamängder?

S: Bubblesortering är inte lämplig för stora datamängder eftersom den är ineffektiv.

F: Hur går bubbelsortering till?

S: Bubblesortering innebär att man jämför intilliggande element i en lista och byter ut dem om de är i fel ordning.

F: Vad kan man säga om komplexiteten hos bubblesortering?

S: Den värsta och genomsnittliga tidskomplexiteten för bubblesortering är O(n^2), vilket innebär att det kan ta mycket lång tid att sortera stora datamängder.

Relaterade artiklar

Författare

AlegsaOnline.com Bubblessortering (bubble sort) – grundläggande algoritm och egenskaper

URL: https://sv.alegsaonline.com/art/14976

Dela