Bidirectional Bubblesort

Bidirectional Bubblesort

Lidt om algoritmen:
Bidirectional bubble sort er en afart af bubble sort, hvor istedet for kun at sortere fremad i listen som er tilfældet med bubble sort, så sorteres der her også baglæns 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.
Bidirectional bubble sort er en anelse hurtigere end bubble sort.

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

Eksemplet er implementeret på et array.
MyBidirectionalBubbleSort.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-BidirectionalBubble sort.

Det eneste while løkken gør er at løbe frem gennem listen.
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 første for løkke løber frem i arrayet og foretager eventuelle ombytninger. Hvis dette sker sættes swapped til true.

Herefter begynder den anden for løkke at løbe baglæns i listen og foretager eventuelle ombytninger i arrayet. Hvis dette sker sættes swapped til true.

While løkken gentages indtil der ikke foretages flere ombygninger, eller at start bliver lig length.