Bubbelsortering
From Wikipedia, the free encyclopedia
Bubbelsortering (engelska Bubble sort) är en enkel, dock inte särskilt effektiv, sorteringsalgoritm.
Snabbfakta Klass, Datastruktur ...
Klass | Sorteringsalgoritm |
---|---|
Datastruktur | array |
Tidskomplexitet värsta fall | O(n2) |
Tidskomplexitet bästa fall | O(n) |
Tidskomplexitet genomsnitt | O(n2) |
Minneskomplexitet värsta fall | O(n) |
Stäng
Algoritmen innebär att det område av en lista som skall sorteras gås igenom upprepade gånger och parvisa jämförelser görs av intilliggande element. Om elementen är i fel ordning kastas elementens ordning om. Efter varje genomgång av ett område kommer det sista talet att ha hamnat på rätt plats. Vid nästa genomgång reduceras därför det område som gås igenom med ett. Efter hand som sorteringen fortlöper kommer den korrekt sorterade delen i botten av listan att växa med ett element per genomgång av den ännu osorterade delen av listan och de ännu osorterade elementen "bubblar" uppåt, därav namnet på sorteringsalgoritmen.