Bubble Sort ist ein einfacher Sortieralgorithmus, der die Liste wiederholt durchläuft, benachbarte Elemente vergleicht und sie vertauscht, wenn sie in der falschen Reihenfolge sind. Der Name „Bubble Sort“ beruht darauf, dass kleinere Elemente an den Anfang der Liste „blasen“. Obwohl er nicht der effizienteste Sortieralgorithmus ist, ist er leicht zu verstehen und zu implementieren, was ihn zu einem guten Ausgangspunkt für das Erlernen von Sortieralgorithmen macht. In diesem Artikel werden wir uns mit dem Konzept der Blasensortierung befassen, eine Python-Implementierung mit Ausgabe bereitstellen und die zeitliche Komplexität des Algorithmus diskutieren.

Blasensortierung verstehen

Die Grundidee hinter Bubble Sort besteht darin, die Liste mehrmals zu durchlaufen, benachbarte Elemente zu vergleichen und sie auszutauschen, wenn sie nicht in der richtigen Reihenfolge sind. Der Vorgang wird fortgesetzt, bis kein Austausch mehr erforderlich ist. Dies zeigt an, dass die Liste nun sortiert ist. Der Name des Algorithmus geht auf die Art und Weise zurück, wie sich kleinere Elemente nach und nach an den Anfang der Liste bewegen, ähnlich wie Blasen, die an die Oberfläche steigen.

Javascript onclick

Lassen Sie uns die Schritte des Bubble-Sort-Algorithmus aufschlüsseln:

1. Durchlaufen Sie die Liste: Beginnen Sie am Anfang der Liste und vergleichen Sie jedes Paar benachbarter Elemente.
2. Vergleichen und tauschen: Wenn die Elemente in der falschen Reihenfolge sind, tauschen Sie sie aus. Dadurch wird sichergestellt, dass das größere Element „nach oben sprudelt“ und das kleinere nach unten wandert.
3. Weiter iterieren: Wiederholen Sie den Vorgang für jedes Paar benachbarter Elemente, bis das Ende der Liste erreicht ist.
4. Bis zur Sortierung wiederholen: Durchlaufen Sie die Liste so lange, bis keine weiteren Swaps mehr erforderlich sind. An diesem Punkt ist die Liste sortiert.

Obwohl Bubble Sort einfach zu verstehen ist, ist es nicht der effizienteste Sortieralgorithmus, insbesondere für große Datensätze. Seine zeitliche Komplexität beträgt im schlimmsten Fall O(n^2), wobei „n“ die Anzahl der Elemente in der Liste ist. Aufgrund dieser quadratischen Zeitkomplexität eignet es sich im Vergleich zu fortgeschritteneren Sortieralgorithmen weniger für große Datensätze.

Python-Implementierung von Bubble Sort

Jetzt implementieren wir Bubble Sort in Python und beobachten sein Verhalten anhand einer Beispielliste:

 def bubble_sort(arr): n = len(arr) # Traverse through all array elements for i in range(n): # Last i elements are already sorted, so we don't need to check them for j in range(0, n-i-1): # Swap if the element found is greater than the next element if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # Example usage if __name__ == '__main__': # Sample list to be sorted sample_list = [64, 34, 25, 12, 22, 11, 90] # Display the original list print('Original List:', sample_list) # Apply Bubble Sort bubble_sort(sample_list) # Display the sorted list print('Sorted List:', sample_list) 

In dieser Implementierung verwendet die Funktion bubble_sort eine Liste (arr) als Parameter und sortiert sie direkt. Die verschachtelte Schleife vergleicht benachbarte Elemente und vertauscht sie, wenn sie in der falschen Reihenfolge sind. Die äußere Schleife stellt sicher, dass der Vorgang wiederholt wird, bis die gesamte Liste sortiert ist.

Ausgabe und Erläuterung

Lassen Sie uns den bereitgestellten Python-Code mit der Beispielliste ausführen und die Ausgabe beobachten:

 Original List: [64, 34, 25, 12, 22, 11, 90] Sorted List: [11, 12, 22, 25, 34, 64, 90] 

Hier wird die ursprüngliche Liste [64, 34, 25, 12, 22, 11, 90] erfolgreich mit dem Bubble-Sort-Algorithmus sortiert, was zur sortierten Liste [11, 12, 22, 25, 34, 64, 90] führt.

Der Algorithmus durchläuft die Liste mehrmals und vergleicht und tauscht Elemente aus, bis die gesamte Liste sortiert ist. Bei jedem Durchgang „blubbert“ das größte unsortierte Element an seine richtige Position. Dieser Vorgang wird fortgesetzt, bis keine weiteren Swaps mehr erforderlich sind, was anzeigt, dass die Liste vollständig sortiert ist.

Während Bubble Sort die Liste erfolgreich sortiert, ist es wichtig zu beachten, dass es aufgrund seiner zeitlichen Komplexität bei großen Datensätzen im Vergleich zu anderen Sortieralgorithmen wie Merge Sort oder Quick Sort weniger effizient ist.

Zeitkomplexität der Blasensortierung

Android-Versionen

Das Verständnis der zeitlichen Komplexität eines Algorithmus ist entscheidend für die Bewertung seiner Effizienz, insbesondere beim Umgang mit großen Datenmengen. Die zeitliche Komplexität von Bubble Sort beträgt im schlimmsten Fall O(n^2), wobei „n“ die Anzahl der Elemente in der Liste ist.

Lassen Sie uns die Zeitkomplexitätsanalyse aufschlüsseln:

• Die äußere Schleife wird für „n“ Iterationen ausgeführt, wobei „n“ die Anzahl der Elemente in der Liste ist.
• Im schlimmsten Fall läuft die innere Schleife auch über 'n' Iterationen. Mit fortschreitendem Algorithmus nimmt jedoch die Anzahl der Iterationen in der inneren Schleife ab, da das größte unsortierte Element bei jedem Durchgang an der richtigen Position platziert wird.
• Im schlimmsten Fall ist die Anzahl der Vergleiche und Vertauschungen proportional zum Quadrat der Anzahl der Elemente in der Liste, was zu einer Zeitkomplexität von O(n^2) führt. Dies macht die Blasensortierung für große Datenmengen ineffizient und in realen Anwendungen werden häufig fortschrittlichere Sortieralgorithmen mit besserer Zeitkomplexität bevorzugt.

Abschluss

In diesem Artikel haben wir das Konzept der Blasensortierung untersucht, einen einfachen Sortieralgorithmus, der benachbarte Elemente wiederholt vergleicht und vertauscht, bis die gesamte Liste sortiert ist. Wir haben eine Python-Implementierung von Bubble Sort bereitgestellt, sie mit einer Beispielliste ausgeführt und die Ausgabe analysiert. Darüber hinaus haben wir die zeitliche Komplexität der Blasensortierung diskutiert und dabei ihre O(n^2)-Zeitkomplexität im ungünstigsten Fall und ihre Auswirkungen auf die Effizienz hervorgehoben.