Blasensortierung in Java

1. Einleitung

In diesem kurzen Artikel werden wir den Bubble Sort-Algorithmus im Detail untersuchen und uns dabei auf eine Java-Implementierung konzentrieren.

Dies ist einer der einfachsten Sortieralgorithmen. Die Kernidee besteht darin , benachbarte Elemente eines Arrays weiter auszutauschen, wenn sie in einer falschen Reihenfolge vorliegen, bis die Sammlung sortiert ist.

Kleine Elemente „sprudeln“ an die Spitze der Liste, während wir die Datenstruktur durchlaufen. Daher ist die Technik als Blasensortierung bekannt.

Da die Sortierung durch Tauschen erfolgt, können wir sagen, dass die Sortierung direkt durchgeführt wird.

Auch wenn zwei Elemente gleiche Werte haben, sich ergebenden Daten werden ihre Bestellung erhalten - das es eine stabile Art macht.

2. Methodik

Wie bereits erwähnt, durchlaufen wir zum Sortieren eines Arrays dieses Array, vergleichen benachbarte Elemente und tauschen sie bei Bedarf aus. Für ein Array der Größe n führen wir n-1 solcher Iterationen durch.

Nehmen wir ein Beispiel, um die Methodik zu verstehen. Wir möchten das Array in aufsteigender Reihenfolge sortieren:

4 2 1 6 3 5

Wir beginnen die erste Iteration mit dem Vergleich von 4 und 2; Sie sind definitiv nicht in der richtigen Reihenfolge. Das Tauschen würde führen zu:

[2 4] 1 6 3 5

Wiederholen Sie dies nun für 4 und 1:

2 [1 4] 6 3 5

Wir machen es bis zum Ende:

2 1 [ 4 6] 3 5

2 1 4 [3 6] 5

2 1 4 3 [5 6]

Wie wir sehen können, haben wir am Ende der ersten Iteration das letzte Element an seiner richtigen Stelle. Jetzt müssen wir nur noch das gleiche Verfahren in weiteren Iterationen wiederholen. Außer, wir schließen die Elemente aus, die bereits sortiert sind.

In der zweiten Iteration durchlaufen wir das gesamte Array mit Ausnahme des letzten Elements. In ähnlicher Weise lassen wir für die 3. Iteration die letzten beiden Elemente weg. Im Allgemeinen iterieren wir für die k-te Iteration bis zum Index nk (ausgeschlossen). Am Ende von n-1 Iterationen erhalten wir das sortierte Array.

Nachdem Sie die Technik verstanden haben, wollen wir uns mit der Implementierung befassen.

3. Implementierung

Implementieren wir die Sortierung für das Beispielarray, das wir mit dem Java 8-Ansatz besprochen haben:

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; } }); }

Und ein kurzer JUnit-Test für den Algorithmus:

@Test public void whenSortedWithBubbleSort_thenGetSortedArray() { Integer[] array = { 2, 1, 4, 6, 3, 5 }; Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 }; BubbleSort bubbleSort = new BubbleSort(); bubbleSort.bubbleSort(array); assertArrayEquals(array, sortedArray); }

4. Komplexität und Optimierung

Wie wir sehen können , für den durchschnittlichen und den schlimmsten Fall , ist die Zeitkomplexität O (n ^ 2) .

Darüber hinaus beträgt die Speicherplatzkomplexität selbst im schlimmsten Fall O (1), da der Bubble-Sortieralgorithmus keinen zusätzlichen Speicher benötigt und die Sortierung im ursprünglichen Array erfolgt.

Durch sorgfältige Analyse der Lösung können wir feststellen, dass wir keine weiteren Iterationen durchführen müssen, wenn in einer Iteration keine Swaps gefunden werden .

Im Fall des zuvor diskutierten Beispiels erhalten wir nach der 2. Iteration:

1 2 3 4 5 6

In der dritten Iteration müssen wir kein Paar benachbarter Elemente austauschen. So können wir alle verbleibenden Iterationen überspringen.

Im Falle eines sortierten Arrays ist ein Austausch in der ersten Iteration selbst nicht erforderlich - was bedeutet, dass wir die Ausführung stoppen können. Dies ist das beste Szenario, und die zeitliche Komplexität des Algorithmus beträgt O (n) .

Lassen Sie uns nun die optimierte Lösung implementieren.

public void optimizedBubbleSort(Integer[] arr) { int i = 0, n = arr.length; boolean swapNeeded = true; while (i < n - 1 && swapNeeded) { swapNeeded = false; for (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++; } }

Lassen Sie uns die Ausgabe für den optimierten Algorithmus überprüfen:

@Test public void givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray() { Integer[] array = { 2, 1, 4, 6, 3, 5 }; Integer[] sortedArray = { 1, 2, 3, 4, 5, 6 }; BubbleSort bubbleSort = new BubbleSort(); bubbleSort.optimizedBubbleSort(array); assertArrayEquals(array, sortedArray); }

5. Schlussfolgerung

In diesem Tutorial haben wir gesehen, wie Bubble Sort funktioniert und wie es in Java implementiert wird. Wir haben auch gesehen, wie es optimiert werden kann. Zusammenfassend ist es ein an Ort und Stelle stabiler Algorithmus mit zeitlicher Komplexität:

  • Schlimmster und durchschnittlicher Fall: O (n * n), wenn das Array in umgekehrter Reihenfolge ist
  • Bester Fall: O (n), wenn das Array bereits sortiert ist

Der Algorithmus ist in der Computergrafik beliebt, da er einige kleine Fehler bei der Sortierung erkennen kann. In einem fast sortierten Array müssen beispielsweise nur zwei Elemente ausgetauscht werden, um ein vollständig sortiertes Array zu erhalten. Die Blasensortierung kann solche Fehler (dh das Sortieren dieses Arrays) in linearer Zeit beheben.

Der Code für die Implementierung dieses Algorithmus ist wie immer auf GitHub zu finden.