TUTORIAL · Algorithm
Blasensortierung rekursiv
In diesem Lernprogramm wird gezeigt, wie Sie mit dem rekursiven Bubble-Sort-Algorithmus eine Sortierung auf einem Array durchführen.
Auf dieser Seite
Bubble Sort ist ein einfacher Sortieralgorithmus. Er funktioniert durch wiederholte Vergleiche benachbarter Elemente und deren Vertauschung, wenn sie in der falschen Reihenfolge sind. Durch die wiederholten Vergleiche wird das kleinste/größte Element an das Ende des Arrays geblasen, daher wird dieser Algorithmus Bubble-Sort genannt. Obwohl er ineffizient ist, stellt er dennoch die Grundlage für Sortieralgorithmen dar.
Bubble Sort Rekursiver Algorithmus
Nehmen wir an, dass wir ein unsortiertes Array A[] mit n Elementen haben.
-
Wenn die Größe des Arrays
A1ist, dann ist das Array bereits sortiert. Also, zurückgeben. -
Andernfalls führen Sie einen Durchgang der iterativen Blasensortierung auf dem angegebenen Unterarray durch. Dabei wird das letzte Element an die richtige Position gesetzt.
-
Verwenden Sie den Rekursionsaufruf, um die obigen Schritte erneut auf einem kleineren Subarray mit um eins reduzierter Größe durchzuführen.
Beispiel für einen rekursiven Bubble-Sort-Algorithmus
Angenommen, wir haben das Array: (5,3,4,2,1). Wir werden es mit dem Bubble-Sort-Algorithmus sortieren.
- Erster Durchlauf:
| (5 3 4 2 1) | → | (3 5 4 2 1) | (3 < 5 vertauscht) |
| (3 5 4 2 1) | → | (3 4 5 2 1) | (4 < 5 vertauscht) |
| (3 4 5 2 1) | → | (3 4 2 5 1) | (2 < 5 vertauscht) |
| (3 4 2 5 1) | → | (3 4 2 1 5) | (1 < 5 vertauscht) |
- Zweiter Durchgang:
| (3 4 2 1 5) | → | (3 4 2 1 5) | |
| (3 4 2 1 5) | → | (3 2 4 1 5) | (2 < 4 vertauscht) |
| (3 2 4 1 5) | → | (3 2 1 4 5) | (1 < 4 vertauscht) |
- Dritter Durchgang:
| (3 2 1 4 5) | → | (2 3 1 4 5) | (2 < 3 vertauscht) |
| (2 3 1 4 5) | → | (2 1 3 4 5) | (1 < 3 vertauscht) |
- Vierter Durchgang:
| (2 1 3 4 5) | → | (1 2 3 4 5) | (1 < 2 vertauscht) |
Wir erhalten das sortierte Array nach dem vierten Durchlauf - (1 2 3 4 5)
Bubble Sort Rekursiver Algorithmus Implementierung
#include <bits/stdc++.h>
using namespace std;
void bubbleSort(int arr[], int n) {
if (n == 1) return;
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr[i], arr[i + 1]);
}
}
bubbleSort(arr, n - 1);
}
int main() {
int n = 8;
int arr[8] = {9, 8, 3, 7, 5, 6, 4, 1};
cout << "Input arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
bubbleSort(arr, n); // Sort elements in ascending order
cout << "Output arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
Bubble-Sort-Algorithmus Komplexität
Zeitkomplexität
- Durchschnittlicher Fall
Im Durchschnitt werden n-i Vergleiche im i-ten Durchlauf von Bubble Sort durchgeführt. Wenn es also n Durchläufe gibt, dann kann die durchschnittliche Zeitkomplexität gegeben sein durch
(n-1) + (n-2) + (n-3) ..... + 1 = n*(n-1)/2
Die Zeitkomplexität liegt also in der Größenordnung von O(n2).
- Schlimmster Fall
Der schlechteste Fall tritt ein, wenn das Array umgekehrt sortiert ist und die maximale Anzahl von Vergleichen und Vertauschungen durchgeführt werden muss.
Die Zeitkomplexität im schlimmsten Fall ist O(n2).
- Bester Fall
Der beste Fall tritt ein, wenn das Array bereits sortiert ist, und dann sind nur N Vergleiche erforderlich.
Die Zeitkomplexität im besten Fall ist O(n).
Raumkomplexität
Die Platzkomplexität für diesen Algorithmus ist O(n) aufgrund der rekursiven Aufrufe, die im Stack gespeichert werden.
