Blase sortieren

1. Blasen-Sortieralgorithmus
2. Beispiel für einen Blasensortierungsalgorithmus
3. Implementierung des Bubble-Sort-Algorithmus
4. Komplexität des Bubble-Sort-Algorithmus

Bubble Sort ist ein einfacher Sortieralgorithmus. Er funktioniert durch den wiederholten Vergleich 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 heißt dieser Algorithmus Bubble-Sort. Obwohl er ineffizient ist, stellt er dennoch die Grundlage für Sortieralgorithmen dar.

Blasen-Sortieralgorithmus

Nehmen wir an, dass wir ein unsortiertes Array A[] mit n Elementen haben.

Schritt 1 im obigen Algorithmus wird auch als Durchlauf bezeichnet. Um ein Array der Größe n zu sortieren, sind n-1 Durchgänge erforderlich.

Beispiel für einen Blasensortierungsalgorithmus

Angenommen, wir haben ein Array: (5,3,4,2,1). Wir werden es mit dem Blasensortierungsalgorithmus sortieren.

• Erster Durchlauf:

• Zweiter Durchgang:

• Dritter Durchgang:

• Vierter Durchgang:

Wir erhalten das sortierte Array nach dem vierten Durchlauf - (1 2 3 4 5)

Implementierung des Bubble-Sort-Algorithmus

#include <iostream>

using namespace std;
void bubble_sort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
      }
    }
  }
}
int main() {
  int n = 5;
  int arr[5] = {5, 3, 4, 2, 1};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  bubble_sort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Komplexität des Bubble-Sort-Algorithmus

Zeitkomplexität

• Durchschnittlicher Fall

Im Durchschnitt werden n-i Vergleiche im lten 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), da außer einer temporären Variablen kein zusätzlicher Speicher benötigt wird.