Blasensortierung rekursiv

1. Bubble Sort Rekursiver Algorithmus
2. Beispiel für einen rekursiven Bubble-Sort-Algorithmus
3. Bubble Sort Rekursiver Algorithmus Implementierung
4. Bubble-Sort-Algorithmus Komplexität

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.

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:

• Zweiter Durchgang:

• Dritter Durchgang:

• Vierter Durchgang:

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(n²).

• 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(n²).

• 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.