Boblesortering

Fra Wikipedia, den frie encyklopedi

Boblesortering
[[Fil: Boblesortering av en liste med tall|210x210px|Boblesortering]]
Sort		Sorteringsalgoritme
Datastruktur		Array
Worst-case ytelse		O(n2)
Best-case ytelse		O(n)
Gjennomsnittlig ytelse		O(n2)
Worst-case plass-kompleksitet		O(n) total, O(1) auxiliary
Optimalisert		No

Boblesortering (en. bubble sort) er en svært enkel sorteringsalgoritme, som hovedsakelig brukes i utdanning for å demonstrere sorteringskonsepter.

Algoritmen begynner først i datasettet og sammenligner de to første elementene, og dersom det første er større enn det andre, bytter de plass. Dette gjøres med alle par av etterfølgende elementer gjennom hele datasettet. Deretter begynner algoritmen ved starten igjen, og repeterer inntil ingen elementer må byttes på siste gjennomgang.

Algoritmen er enkel, men lite effektiv og er sjelden brukt unntatt som eksempel i utdanningssammenheng. En noe bedre variant, coctail sort, virker ved å invertere sorteringskriteriet og gjennomgangsretning for hver gjennomgang. For sortering av små datasett er det bedre enn quicksort.