Bubblessortering

Bubble sort är en enkel sorteringsalgoritm. Den är enkel att förstå och lärs därför vanligtvis ut till nya studenter. Den är inte lika effektiv som vissa andra sorteringsalgoritmer.

Namnet Bubble Sort kommer från det faktum att varje objekt i listan "bubblar" upp till den plats där det ska vara, som bubblor i vatten.

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.

Genomförande

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

Ställ in flaggan sorterad.
Börja i ena änden och betrakta varje angränsande par av element i en vektor efter varandra (i deras ordning).
Om ett pars element är oordnade byter du dem och rensar flaggan.
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.