Eine Einführung in den Bubble-Sort-Algorithmus

Das Sortieren ist eine der grundlegendsten Operationen, die Sie auf Daten anwenden können. Sie können Elemente in verschiedenen Programmiersprachen mit verschiedenen Sortieralgorithmen wie Quick Sort, Bubble Sort, Merge Sort, Insertion Sort usw. sortieren. Bubble Sort ist der einfachste Algorithmus von all diesen.

In diesem Artikel erfahren Sie mehr über die Funktionsweise des Bubble Sort-Algorithmus, dem Pseudocode des Bubble Sort S Algorithmus, seine Zeit- und Raumkomplexität und seine Implementierung in verschiedenen Programmiersprachen wie C++, Python, C und JavaScript.

Wie funktioniert der Bubble-Sort-Algorithmus?

Bubble Sort ist der einfachste Sortieralgorithmus, der die Liste wiederholt durchläuft, benachbarte Elemente vergleicht und sie vertauscht, wenn sie in der falschen Reihenfolge sind. Dieses Konzept lässt sich anhand eines Beispiels effizienter erklären. Betrachten Sie ein unsortiertes Array mit den folgenden Elementen: {16, 12, 15, 13, 19}.

Beispiel:

Hier werden die benachbarten Elemente verglichen und wenn sie nicht in aufsteigender Reihenfolge sind, werden sie vertauscht.

Pseudocode des Bubble-Sort-Algorithmus

Im Pseudocode, kann der Bubble-Sort-Algorithmus wie folgt ausgedrückt werden:

BubbleSort (Arr[], Größe)
// Schleife, um auf jedes Array-Element zuzugreifen
für i=0 bis Größe-1 tun Sie:
// Schleife zum Vergleichen von Array-Elementen
für j=0 bis Größe-i-1 tun Sie:
// vergleiche die benachbarten Elemente
wenn Arr[j] > Arr[j+1] dann
// tausche sie aus
tauschen (Arr[j], Arr[j+1])
ende wenn
Ende für
Ende für
Ende

Der obige Algorithmus verarbeitet alle Vergleiche, auch wenn das Array bereits sortiert ist. Es kann weiter optimiert werden, indem der Algorithmus gestoppt wird, wenn die innere Schleife keinen Swap verursacht hat. Dadurch wird die Ausführungszeit des Algorithmus verkürzt.

Somit kann der Pseudocode des optimierten Bubble-Sort-Algorithmus ausgedrückt werden als:

BubbleSort (Arr[], Größe)
// Schleife, um auf jedes Array-Element zuzugreifen
für i=0 bis Größe-1 tun Sie:
// prüfen, ob Swapping stattfindet
getauscht = falsch
// Schleife zum Vergleichen von Array-Elementen
für j=0 bis Größe-i-1 tun Sie:
// vergleiche die benachbarten Elemente
wenn Arr[j] > Arr[j+1] dann
// tausche sie aus
tauschen (Arr[j], Arr[j+1])
getauscht = wahr
ende wenn
Ende für
// Wenn keine Elemente vertauscht wurden, bedeutet dies, dass das Array jetzt sortiert ist, dann unterbreche die Schleife.
wenn (nicht getauscht) dann
Unterbrechung
ende wenn
Ende für
Ende

Zeitkomplexität und Hilfsraum des Bubble-Sort-Algorithmus

Die Worst-Case-Zeitkomplexität des Bubble-Sort-Algorithmus ist O(n^2). Es tritt auf, wenn das Array in absteigender Reihenfolge angeordnet ist und Sie es in aufsteigender Reihenfolge sortieren möchten oder umgekehrt.

Die Zeitkomplexität des Bubble-Sort-Algorithmus im besten Fall ist O(n). Es tritt auf, wenn das Array bereits sortiert ist.

Verbunden: Was ist Big-O-Notation?

Die durchschnittliche Zeitkomplexität des Bubble-Sort-Algorithmus beträgt O(n^2). Es tritt auf, wenn die Elemente des Arrays in einer durcheinandergebrachten Reihenfolge sind.

Der für den Bubble-Sort-Algorithmus benötigte Hilfsraum ist O(1).

C++-Implementierung des Bubble-Sort-Algorithmus

Unten ist die C++-Implementierung des Bubble-Sort-Algorithmus:

// C++-Implementierung des
// optimierter Bubble-Sort-Algorithmus
#einschließen 
Verwenden des Namensraums std;
// Funktion zum Ausführen von Bubble Sort
void bubbleSort (int arr[], int Größe) {
// Schleife um auf jedes Element des Arrays zuzugreifen
für (int i=0; i// Variable, um zu überprüfen, ob ein Austausch stattfindet
bool vertauscht = false;
// Schleife, um zwei benachbarte Elemente des Arrays zu vergleichen
für (intj = 0; j < (Größe-i-1); j++) {
// Vergleich zweier benachbarter Array-Elemente
if (arr[j] > arr[j + 1]) {
// Vertausche beide Elemente, wenn sie sind
// nicht in der richtigen Reihenfolge
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
getauscht = wahr;
}
}
// Wenn keine Elemente vertauscht wurden, bedeutet dies, dass das Array jetzt sortiert ist,
// dann die Schleife unterbrechen.
if (ausgetauscht == false) {
Unterbrechung;
}
}
}
// Gibt die Elemente des Arrays aus
void printArray (int arr[], int Größe) {
für (int i = 0; ich < Größe; ich++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {16, 12, 15, 13, 19};
// Ermitteln der Länge des Arrays
int size = sizeof (arr) / sizeof (arr[0]);
// Ausgabe des angegebenen unsortierten Arrays
cout << "Unsortiertes Array: " << endl;
printArray (arr, Größe);
// Aufruf der Funktion bubbleSort()
BubbleSort (arr, Größe);
// Drucken des sortierten Arrays
cout << "Sortiertes Array in aufsteigender Reihenfolge:" << endl;
printArray (arr, Größe);
0 zurückgeben;
}

Ausgabe:

Unsortiertes Array: 
16 12 15 13 19 
Sortiertes Array in aufsteigender Reihenfolge:
12 13 15 16 19

Python-Implementierung des Bubble-Sort-Algorithmus

Unten ist die Python-Implementierung des Bubble-Sort-Algorithmus:

# Python-Implementierung des
# optimierter Bubble-Sort-Algorithmus
# Funktion zum Ausführen von Bubble Sort
def bubbleSort (arr, Größe):
# Schleife, um auf jedes Element der Liste zuzugreifen
für i im Bereich (Größe-1):
# Variable, um zu überprüfen, ob ein Austausch stattfindet
vertauscht = Falsch
# Schleife, um zwei benachbarte Elemente der Liste zu vergleichen
für j im Bereich (Größe-i-1):
# Vergleich zweier benachbarter Listenelemente
if arr[j] > arr[j+1]:
temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
getauscht = wahr
# Wenn keine Elemente vertauscht wurden, bedeutet dies, dass die Liste jetzt sortiert ist,
# dann unterbrechen Sie die Schleife.
wenn getauscht == Falsch:
Unterbrechung
# Druckt die Elemente der Liste
def printArray (arr):
für Element in arr:
print (element, end="")
drucken("")
arr = [16, 12, 15, 13, 19]
# Ermitteln der Länge der Liste
Größe = len (arr)
# Drucken der angegebenen unsortierten Liste
print("Unsortierte Liste:")
printArray (arr)
# Aufruf der Funktion bubbleSort()
BubbleSort (arr, Größe)
# Drucken der sortierten Liste
print("Sortierte Liste in aufsteigender Reihenfolge:")
printArray (arr)

Ausgabe:

Unsortierte Liste:
16 12 15 13 19 
Sortierte Liste in aufsteigender Reihenfolge:
12 13 15 16 19

Verbunden: So verwenden Sie For-Schleifen in Python

C Implementierung des Bubble-Sort-Algorithmus

Unten ist die C-Implementierung des Bubble-Sort-Algorithmus:

// C-Implementierung des
// optimierter Bubble-Sort-Algorithmus
#einschließen 
#einschließen 
// Funktion zum Ausführen von Bubble Sort
void bubbleSort (int arr[], int Größe) {
// Schleife um auf jedes Element des Arrays zuzugreifen
für (int i=0; i// Variable, um zu überprüfen, ob ein Austausch stattfindet
bool vertauscht = false;
// Schleife, um zwei benachbarte Elemente des Arrays zu vergleichen
für (intj = 0; j < (Größe-i-1); j++) {
// Vergleich zweier benachbarter Array-Elemente
if (arr[j] > arr[j + 1]) {
// Vertausche beide Elemente, wenn sie sind
// nicht in der richtigen Reihenfolge
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
getauscht = wahr;
}
}
// Wenn keine Elemente vertauscht wurden, bedeutet dies, dass das Array jetzt sortiert ist,
// dann die Schleife unterbrechen.
if (ausgetauscht == false) {
Unterbrechung;
}
}
}
// Gibt die Elemente des Arrays aus
void printArray (int arr[], int Größe) {
für (int i = 0; ich < Größe; ich++) {
printf("%d", arr[i]);
}
printf(" \⁠n ");
}
int main() {
int arr[] = {16, 12, 15, 13, 19};
// Ermitteln der Länge des Arrays
int size = sizeof (arr) / sizeof (arr[0]);
// Ausgabe des angegebenen unsortierten Arrays
printf("Unsortiertes Array: \⁠n");
printArray (arr, Größe);
// Aufruf der Funktion bubbleSort()
BubbleSort (arr, Größe);
// Drucken des sortierten Arrays
printf("Sortiertes Array in aufsteigender Reihenfolge: \⁠n");
printArray (arr, Größe);
0 zurückgeben;
}

Ausgabe:

Unsortiertes Array: 
16 12 15 13 19 
Sortiertes Array in aufsteigender Reihenfolge: 
12 13 15 16 19

JavaScript-Implementierung des Bubble-Sort-Algorithmus

Unten sehen Sie die JavaScript-Implementierung des Bubble-Sort-Algorithmus:

// JavaScript-Implementierung des
// optimierter Bubble-Sort-Algorithmus
// Funktion zum Ausführen von Bubble Sort
Funktion bubbleSort (arr, Größe) {
// Schleife um auf jedes Element des Arrays zuzugreifen
für (lassen Sie i = 0; ich// Variable, um zu überprüfen, ob ein Austausch stattfindet
var vertauscht = false;
// Schleife, um zwei benachbarte Elemente des Arrays zu vergleichen
für (es sei j = 0; j// Vergleich zweier benachbarter Array-Elemente
if (arr[j] > arr[j+1]) {
// Vertausche beide Elemente, wenn sie sind
// nicht in der richtigen Reihenfolge
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
getauscht = wahr;
}
// Wenn keine Elemente vertauscht wurden, bedeutet dies, dass das Array jetzt sortiert ist,
// dann die Schleife unterbrechen.
if (ausgetauscht == false) {
Unterbrechung;
}
}
}
}
// Gibt die Elemente des Arrays aus
Funktion printArray (arr, Größe) {
für (lassen Sie i = 0; ichdocument.write (arr[i] + " ");
}
document.write("
")
}
var arr = [16, 12, 15, 13, 19];
// Ermitteln der Länge des Arrays
Var-Größe = Arr.Länge;
// Ausgabe des angegebenen unsortierten Arrays
document.write("Unsortiertes Array: 
");
printArray (arr, Größe);
// Aufruf der Funktion bubbleSort()
BubbleSort (arr, Größe);
// Drucken des sortierten Arrays
document.write("Sortiertes Array in aufsteigender Reihenfolge: 
");
printArray (arr, Größe);

Ausgabe:

Unsortiertes Array:
16 12 15 13 19
Sortiertes Array in aufsteigender Reihenfolge:
12 15 13 16 19

Jetzt verstehen Sie die Funktionsweise des Bubble-Sort-Algorithmus

Bubble Sort ist der einfachste Sortieralgorithmus und wird hauptsächlich verwendet, um die Grundlagen des Sortierens zu verstehen. Bubble Sort kann auch rekursiv implementiert werden, bietet aber keine zusätzlichen Vorteile.

Mit Python können Sie den Bubble-Sort-Algorithmus ganz einfach implementieren. Wenn Sie mit Python nicht vertraut sind und Ihre Reise beginnen möchten, ist es eine gute Wahl, mit einem "Hello World"-Skript zu beginnen.

Erste Schritte mit Python mit einem "Hello World"-Skript

Python ist heute eine der beliebtesten Programmiersprachen. Folgen Sie diesem Tutorial, um mit Ihrem allerersten Python-Skript zu beginnen.

Weiter lesen

Über den Autor