Boblesortering

Bubblesort redigerede farve

Boblesortering (eng. bubble sort) er en populær sorteringsalgoritme og er en af de simpleste algoritmer at forstå og implementere. Dog er den ikke en særlig effektiv sorteringsalgoritme; hverken for store eller små lister, og den anvendes meget sjældent i praksis. Boblesortering sorterer som navnet antyder, elementerne i en liste ved at ombytte (boble) et element ad gangen, så det kommer på sin rette plads i listen.

Algoritmen

Boblesorteringsalgoritmen illustreres ved et eksempel. På figuren svarer de grå felter til de elementer, der er sorteret færdigt, og de røde felter svarer til de to elementer, der sammenlignes. Det blå felt svarer til det element, der skal sammenlignes med til sidst i den pågældende iteration. Algoritmen starter med at sammenligne de sidste to elementer i listen og ”farver” det første felt blåt. Hvis de to røde elementer står i den forkerte rækkerfølge, ombyttes de. Algoritmen undersøger derefter de næste to elementer, og de ombyttes, hvis de også står i den forkerte rækkefølge, figur (a) – (c). På figur (d) bliver det blå felt sammenlignet med elementet ved siden af. På figur (e) er den værdi der skal være på første felt færdigsorteret, og det andet felt bliver nu farvet blåt. Nu bliver de sidste to elementer sammenlignet på ny, og proceduren gentages. Nederst på illustrationen er den færdigsorterede liste vist, figur (o).

Beregningskompleksiteten

Algoritmens tidskompleksitet er i værste tilfælde kvadratisk i køretid Θ(n²).