streamalism.org

1. Inleiding

In dit korte artikel zullen we het Bubble Sort-algoritme in detail onderzoeken, met de nadruk op een Java-implementatie.

Dit is een van de meest eenvoudige sorteeralgoritmen; het kernidee is omblijf aangrenzende elementen verwisselen van een array als ze in de verkeerde volgorde staan ​​totdat de collectie is gesorteerd.

Kleine items "bubbelen" naar de top van de lijst terwijl we de datastructuur herhalen. Daarom staat de techniek bekend als bellen sorteren.

Omdat sorteren wordt uitgevoerd door te wisselen, kunnen we zeggen dat het sorteren ter plaatse uitvoert.

Ook, als twee elementen dezelfde waarden hebben, blijft de volgorde van de resulterende gegevens behouden - wat het een stabiele soort maakt.

2. Methodologie

Zoals eerder vermeld, om een ​​array te sorteren, itereren we er doorheen terwijl we aangrenzende elementen vergelijken en ze indien nodig verwisselen. Voor een reeks afmetingen n, wij treden op n-1 dergelijke iteraties.

Laten we een voorbeeld nemen om de methodologie te begrijpen. We willen de array in oplopende volgorde sorteren:

4 2 1 6 3 5

We starten de eerste iteratie door 4 en 2 te vergelijken; ze zijn beslist niet in de juiste volgorde. Ruilen zou resulteren in:

[2 4] 1 6 3 5

Herhaal nu hetzelfde voor 4 en 1:

2 [14] 6 3 5

We blijven het doen tot het einde:

2 1 [4 6] 3 5

2 1 4 [36] 5

2 1 4 3 [5 6]

Zoals we kunnen zien, kregen we aan het einde van de eerste iteratie het laatste element op zijn rechtmatige plaats. Nu hoeven we alleen nog maar dezelfde procedure te herhalen in verdere iteraties. Behalve dat we de elementen uitsluiten die al zijn gesorteerd.

In de tweede iteratie zullen we de hele array doorlopen, behalve het laatste element. Evenzo laten we voor de 3e iteratie de laatste 2 elementen weg. In het algemeen herhalen we voor k-de iteratie tot index n-k (uitgesloten). Aan het einde van n-1 iteraties, we krijgen de gesorteerde array.

Nu u de techniek begrijpt, gaan we dieper ingaan op de implementatie.

3. Implementatie

Laten we de sortering implementeren voor de voorbeeldarray die we hebben besproken met behulp van de Java 8-benadering:

void bubbleSort (Integer [] arr) {int n = arr.length; IntStream.range (0, n - 1) .flatMap (i -> IntStream.range (1, n - i)) .forEach (j -> {if (arr [j - 1]> arr [j]) {int temp = arr [j]; arr [j] = arr [j - 1]; arr [j - 1] = temp;}}); }

En een snelle JUnit-test voor het algoritme:

@Test openbare leegte whenSortedWithBubbleSort_thenGetSortedArray () {Integer [] array = {2, 1, 4, 6, 3, 5}; Geheel getal [] sortArray = {1, 2, 3, 4, 5, 6}; BubbleSort bubbleSort = nieuwe BubbleSort (); bubbleSort.bubbleSort (matrix); assertArrayEquals (array, sortedArray); }

4. Complexiteit en optimalisatie

Zoals we kunnen zien, voor het gemiddelde en het ergste geval, de tijdcomplexiteit isO (n ^ 2).

Daarnaast, de complexiteit van de ruimte, zelfs in het ergste scenario, is O (1) omdat het Bubble-sorteeralgoritme geen extra geheugen nodig heeft en het sorteren vindt plaats in de originele array.

Door de oplossing zorgvuldig te analyseren, kunnen we dat zien als er geen swaps worden gevonden in een iteratie, hoeven we niet verder te itereren.

In het geval van het eerder besproken voorbeeld, krijgen we na de 2e iteratie:

1 2 3 4 5 6

In de derde iteratie hoeven we geen paar aangrenzende elementen om te wisselen. We kunnen dus alle resterende iteraties overslaan.

In het geval van een gesorteerde array is wisselen niet nodig in de eerste iteratie zelf - wat betekent dat we de uitvoering kunnen stoppen. Dit is het beste scenario en het tijdcomplexiteit van het algoritme is O (n).

Laten we nu de geoptimaliseerde oplossing implementeren.

openbare leegte geoptimaliseerdeBubbleSort (geheel getal [] arr) {int i = 0, n = arr.length; boolean swapNeeded = true; while (i <n - 1 && swapNeeded) {swapNeeded = false; voor (int j = 1; j arr [j]) {int temp = arr [j - 1]; arr [j - 1] = arr [j]; arr [j] = temp; swapNeeded = true; }} if (! swapNeeded) {break; } i ++; }}

Laten we de uitvoer bekijken voor het geoptimaliseerde algoritme:

@Test openbare leegte gegevenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray () {Geheel getal [] array = {2, 1, 4, 6, 3, 5}; Geheel getal [] sortArray = {1, 2, 3, 4, 5, 6}; BubbleSort bubbleSort = nieuwe BubbleSort (); bubbleSort.optimizedBubbleSort (matrix); assertArrayEquals (array, sortedArray); }

5. Conclusie

In deze tutorial hebben we gezien hoe Bubble Sort werkt en hoe het in Java wordt geïmplementeerd. We hebben ook gezien hoe het geoptimaliseerd kan worden. Samenvattend is het een in-place stabiel algoritme, met tijdcomplexiteit:

• Slechtste en gemiddelde geval: O (n * n), wanneer de array in omgekeerde volgorde staat
• Beste geval: O (n), als de array al is gesorteerd

Het algoritme is populair in computergraphics, vanwege zijn vermogen om enkele kleine fouten bij het sorteren te detecteren. In een bijna gesorteerde array hoeven bijvoorbeeld slechts twee elementen te worden verwisseld om een ​​volledig gesorteerde array te krijgen. Bubble Sort kan dergelijke fouten corrigeren (dwz deze array sorteren) in lineaire tijd.

Zoals altijd is de code voor de implementatie van dit algoritme te vinden op GitHub.