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.
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²).
I ett imperativt programmeringsspråk kan bubbelsortering implementeras genom att använda en flaggvariabel och genomgå arrayens element i en loop:
sorterad.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:
S: Bubble sort är en enkel sorteringsalgoritm.
S: Bubblesortering är enkel att förstå, så den lärs vanligtvis ut till nya studenter.
S: Bubble sort är inte lika effektiv som vissa andra sorteringsalgoritmer.
S: Namnet kommer från det faktum att varje objekt i listan "bubblar" upp dit det ska, som bubblor i vatten.
S: Bubblesortering är inte lämplig för stora datamängder eftersom den är ineffektiv.
S: Bubblesortering innebär att man jämför intilliggande element i en lista och byter ut dem om de är i fel ordning.
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.