Bubblesort

Bubblesort

Lidt om algoritmen:
Bubble sort er en meget simpel sorterings algoritme, som fungerer ved at løbe gennem listen og sammenligne elementet med det efterfølgende element.
Hvis det efterfølgende element er mindre end det nuværende element bliver de byttet rundt.
Bubble sort flytter elementer frem i arrayet til deres endelige plads, men kan kun flytte elementer et skridt bagud af gangen for hver gennemløb.
Da mindst et element flyttes til dets endelige plads for hvert gennemløb, kan bubble sort forbedres ved at rykke markøren for det sidste element en ned for hvert gennemløb.

Hvis bubble sort implementeres grafisk ville det se ud som om det største element "boblede" frem i listen.

Hastighed:
Hvis bubble sort implementeres på et usorteret array er det en O(n2).
Hvis den istedet bruges på et sorteret array er den tilnærmelsesvist en O(n) algoritme.

Eksempel:
Sourcekode til eksempel:
SortAlgorithm.java
MyBubbleSort.java

Eksemplet er implementeret på et array.
MyBubbleSort.java indeholder metoden sort( int[] a ) der udfører sorteringen.
Da dette eksempel terminerer så snart der ikke er mere at sortere er det en afart af bubble sort der kaldes Fast-Bubble sort.

Den første for løkke initialiserer marker1 og løber baglæns gennem arrayet.
Den bruges til at indikere hvor den næste forløkke skal stoppe.
Boolean'en swapped indikerer om der er blevet byttet om på nogle elementer i dette gennemløb. Hvis der ikke er blevet byttet om på elementerne i et gennemløb stopper sorteringen.
Den anden for løkke initialiserer marker2 til nul og den tælles op til marker1.
Her løbes der op gennem arrayet og for hvert step sammenlignes det nuværende element med det næste og er det nuværende element størst bytter de plads og swapped sættes til true.