Bubble Sort-Algorithmus in Java: Array-Sortierprogramm und Beispiel

Was ist Bubble Sortieren?

Bubble Sort ist ein einfacher, auf Vergleichen basierender Sortieralgorithmus, der das erste Element des Arrays mit dem nächsten vergleicht. Ist das aktuelle Element numerisch größer als das nächste, werden die Elemente vertauscht. Der Algorithmus durchläuft dabei alle Elemente des Arrays.

Der Algorithmus verdankt seinen Namen der Art und Weise, wie der größte Wert im unsortierten Bereich stetig zu seiner endgültigen Position aufsteigt, ähnlich einer Wasserblase, die an die Oberfläche gelangt. Nach dem ersten Durchlauf befindet sich das größte Element am letzten Index. Nach dem zweiten Durchlauf wird das zweitgrößte Element an seiner Position fixiert, und der Prozess wiederholt sich, bis das Array vollständig sortiert ist.

In diesem Artikel werden wir ein Java Programm zur Umsetzung BubblSortieren Sie die Ergebnisse. Überprüfen Sie die Ausgabe des Codes, um die Programmlogik zu verstehen, und sehen Sie sich anschließend die optimierte Version und die Komplexitätsanalyse an.

Wie funktioniert das? BubblFunktioniert der Sortieralgorithmus?

BubblDer Sortieralgorithmus durchläuft das Array in mehreren Durchläufen. Jeder Durchlauf geht vom ersten Index bis zum Ende des aktuell unsortierten Bereichs, vergleicht benachbarte Werte und tauscht sie.ping Sie werden immer dann verschoben, wenn sie in der falschen Reihenfolge erscheinen. Da der größte verbleibende Wert immer ganz rechts im unsortierten Bereich liegt, verkleinert sich der Bereich nach jedem Durchlauf um genau eine Position.

Der gesamte Prozess lässt sich in vier wiederholbare Schritte unterteilen:

1. Vergleichen Sie: Vergleiche das Element am Index j-1 mit dem Element am Index j.
2. Swap: Ist das linke Element größer als das rechte Element, werden die beiden Werte mithilfe einer temporären Variable vertauscht.
3. Vorauszahlung: Gehen Sie jeweils eine Position nach rechts und wiederholen Sie den Vorgang, bis Sie das Ende des unsortierten Bereichs erreicht haben.
4. Wiederholen: Beginne einen neuen Durchlauf über eine Region, die ein Element kürzer ist, und beende ihn nach n-1 Durchläufen oder wenn ein Durchlauf keine Vertauschungen mehr durchführt.

In der nachstehenden Tabelle tracDas Beispielarray {860, 8, 200, 9}, das später auf dieser Seite im Programm verwendet wird, zeigt genau, welcher Wert am Ende jedes Durchlaufs seine endgültige Position einnimmt.

Beachten Sie, dass im dritten Durchlauf ein Vergleich, aber kein Tausch durchgeführt wird. Eine optimierte Implementierung erkennt diesen Zustand und stoppt sofort. Dies ist die mit Abstand wertvollste Verbesserung, die Sie an diesem Algorithmus vornehmen können.

BubblPseudocode des Sortieralgorithmus

Vor dem Schreiben Java Die Syntax hilft dabei, die Logik in sprachneutralem Pseudocode auszudrücken. Die untenstehende Version enthält das Flag für vorzeitiges Beenden und deckt somit sowohl das klassische als auch das optimierte Verhalten ab.

procedure bubbleSort(array A, integer n)
    for i from 0 to n - 2 do
        swapped := false
        for j from 1 to n - i - 1 do
            // compare the adjacent pair
            if A[j - 1] > A[j] then
                swap A[j - 1] and A[j]
                swapped := true
            end if
        end for
        // no swap in a full pass means the array is sorted
        if swapped = false then
            break
        end if
    end for
end procedure

Die äußere Schleife steuert die Anzahl der Durchläufe, die innere Schleife die Vergleiche innerhalb eines einzelnen Durchlaufs. Die obere Grenze der inneren Schleife ist n – i – 1, da die letzten i Positionen bereits ihre endgültigen Werte enthalten.

Java Programm zur Umsetzung Bubble Sortieren

Das folgende Programm sortiert ein Integer-Array aufsteigend. Zusätzliche print-Anweisungen wurden absichtlich innerhalb der Schleifen eingefügt, da das Lesen der einzelnen Durchläufe schwierig ist. trace ist der schnellste Weg für einen Anfänger zu verstehen, wie sich die Swaps anhäufen.

package com.guru99;

public class BubbleSort {

    public static void main(String[] args)
    {
        int arr[] = {860, 8, 200, 9};

        System.out.println("---Array BEFORE Bubble Sort---");

        printArray(arr);

        bubbleSort(arr); //sorting array elements using bubble sort

        System.out.println("---Array AFTER Bubble Sort---");

        printArray(arr);

    }

    static void bubbleSort(int[] array)
    {
        int n = array.length;
        int temp = 0;
        for(int i = 0; i < n; i++) // Looping through the array length
        {   System.out.println("Sort Pass Number " + (i + 1));
            for(int j = 1; j < (n - i); j++)
            {
                System.out.println("Comparing " + array[j - 1] + " and " + array[j]);
                if(array[j - 1] > array[j])
                {
                    //swap elements
                    temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    System.out.println(array[j] + " is greater than " + array[j - 1]);
                    System.out.println("Swapping Elements: New Array After Swap");
                    printArray(array);
                }

            }
        }

    }

    static void printArray(int[] array){

        for(int i = 0; i < array.length; i++)
        {
            System.out.print(array[i] + " ");
        }
        System.out.println();

    }
}

Ausgang:

---Array BEFORE Bubble Sort---
860 8 200 9
Sort Pass Number 1
Comparing 860 and 8
860 is greater than 8
Swapping Elements: New Array After Swap
8 860 200 9
Comparing 860 and 200
860 is greater than 200
Swapping Elements: New Array After Swap
8 200 860 9
Comparing 860 and 9
860 is greater than 9
Swapping Elements: New Array After Swap
8 200 9 860
Sort Pass Number 2
Comparing 8 and 200
Comparing 200 and 9
200 is greater than 9
Swapping Elements: New Array After Swap
8 9 200 860
Sort Pass Number 3
Comparing 8 and 9
Sort Pass Number 4
---Array AFTER Bubble Sort---
8 9 200 860

Code Erläuterung: Das Bubble-Sort Die Methode erhält das Array als Referenz, sodass der Aufrufer das sortierte Ergebnis ohne Rückgabewert sieht. Die Variable Temp. speichert während des Dreizeilentauschs einen Wert, weshalb der Algorithmus nur O(1) zusätzlichen Speicher benötigt. Der Ausdruck n –i Die Bedingung in der inneren Schleife garantiert, dass bereits sortierte Positionen am Ende der Schleife niemals erneut besucht werden.

Optimiert Bubble Programm sortieren in Java

Das obige Programm führt stets n-1 Durchläufe aus, selbst wenn das Array frühzeitig sortiert ist. Durch Hinzufügen eines einzelnen booleschen Flags lässt sich diese Ineffizienz beheben. Wenn ein vollständiger Durchlauf ohne einen einzigen Tauschvorgang abgeschlossen ist, ist das Array garantiert sortiert und die äußere Schleife kann sofort beendet werden.

package com.guru99;

public class OptimizedBubbleSort {

    public static void main(String[] args) {
        int arr[] = {5, 12, 33, 47, 58};
        bubbleSort(arr);
        System.out.println(java.util.Arrays.toString(arr));
    }

    static void bubbleSort(int[] array) {
        int n = array.length;
        int passes = 0;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 1; j < n - i; j++) {
                if (array[j - 1] > array[j]) {
                    int temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    swapped = true;
                }
            }
            passes++;
            // Early exit: the array is already sorted
            if (!swapped) {
                break;
            }
        }
        System.out.println("Passes executed: " + passes);
    }
}

Ausgang:

Passes executed: 1
[5, 12, 33, 47, 58]

Das Eingabe-Array war bereits sortiert, daher benötigte die optimierte Version nur einen Durchlauf anstatt vier. Bei nahezu sortierten Daten wandelt diese Änderung eine quadratische Arbeitslast in eine nahezu lineare um, was der Hauptgrund dafür ist. Bubble Sort taucht auch heute noch gelegentlich in realem Code auf.

Zeitkomplexität und Speicherkomplexität von Bubble Sortieren

Die Komplexität beschreibt, wie die Laufzeit mit zunehmender Eingabegröße ansteigt. Bubble Sortieren Die Anzahl der Vergleiche in der nicht optimierten Version ist auf n(n-1)/2 festgelegt, was sie eindeutig in die Klasse der quadratischen Algorithmen einordnet.

Weil jeder Austausch innerhalb des ursprünglichen Arrays stattfindet und nur eine temporäre Variable verwendet wird, Bubble Sort ist ein In-Place-Algorithmus mit O(1) zusätzlichem Speicherplatz. Es handelt sich außerdem um einen stabilen Sortieralgorithmus, d. h., zwei Datensätze mit demselben Schlüssel behalten nach dem Sortieren ihre ursprüngliche relative Reihenfolge bei.

Vor- und Nachteile von Bubble Sortieren

Das Verständnis beider Seiten hilft Ihnen zu entscheiden, wann der Algorithmus eine akzeptable Wahl ist und wann er ersetzt werden sollte.

Vorteile

• Einfachheit: Die Logik passt in etwa zehn Zeilen, was es einfach macht, sie unter Interviewbedingungen korrekt zu formulieren.
• Betrieb vor Ort: Es wird kein Hilfsarray zugewiesen, sodass der Speicherverbrauch nicht mit der Eingabegröße ansteigt.
• Stabilität: Gleiche Schlüssel behalten ihre ursprüngliche Reihenfolge, was beim Sortieren von Datensätzen nach einem sekundären Feld wichtig ist.
• Früherkennung des Ausstiegs: Das vertauschte Flag kennzeichnet ein bereits sortiertes Array in einem einzigen Durchlauf.

Nachteile

• Quadratisches Wachstum: Das Sortieren von 10,000 Elementen erfordert im schlimmsten Fall fast 50 Millionen Vergleiche.
• Excessive schreibt: Der Algorithmus führt deutlich mehr Tauschvorgänge durch als Selection Sort, was speicherintensiv ist und langsame Schreibvorgänge erfordert.
• Schlechte Skalierbarkeit: Bei Produktionsworkloads werden fast immer Quicksort, Mergesort oder die integrierte Arrays.sort-Methode bevorzugt.

Bubble-Sortierung vs. andere Sortiermethoden Algorithms

Die folgende Tabelle vergleicht BubblSortieren Sie anschließend mit den Sortiertechniken, die Anfänger kennenlernen, damit Sie genau sehen können, wo jede einzelne ihre Stärken hat.

Bubble Sort und Insertion Sort haben denselben linearen Bestfall, aber Insertion Sort führt bei teilweise sortierten Daten weniger Vertauschungen durch. Selection Sort führt immer genau n-1 Vertauschungen durch, was ihn zu einem linearen Bestfall macht.tracQuicksort oder Heapsort sind die richtige Wahl, wenn Schreibvorgänge aufwändig sind, allerdings auf Kosten der Stabilität. Für Arrays mit mehr als einigen hundert Elementen sind Quicksort oder Heapsort die beste Lösung.

Sobald Sie mit den hier verwendeten Array-Traversierungsmustern vertraut sind, taucht dieselbe Schleifenstruktur in vielen klassischen Übungen auf, wie zum Beispiel in der Fibonacci-Folge in Java und der Java Palindromprogramm. Revansehen Java Arrays und je breiter Java Lernprogramm wird die Grundlagen stärken, auf denen dieser Algorithmus beruht.

Häufig gestellte Fragen