Binäre Sortierung

1. Binärer Sortieralgorithmus
2. Beispiel für binäre Sortierung
3. Implementierung des binären Sortieralgorithmus
4. Binärer Sortieralgorithmus Komplexität

Binäre Sortierung ist ein Sortieralgorithmus vom Typ Vergleichssortierung. Er ist eine Abwandlung des Einfügesortieralgorithmus. Auch bei diesem Algorithmus halten wir ein sortiertes und ein unsortiertes Subarray. Der einzige Unterschied besteht darin, dass wir die korrekte Position eines Elements mit Hilfe der binären Suche statt der linearen Suche finden. Dies hilft, den Sortieralgorithmus zu beschleunigen, indem die Anzahl der erforderlichen Vergleiche reduziert wird.

Binärer Sortieralgorithmus

Nehmen wir an, dass wir ein unsortiertes Array A[] mit n Elementen haben. Das erste Element, A[0], ist bereits sortiert und befindet sich im sortierten Subarray.

Beispiel für binäre Sortierung

Angenommen, wir haben das Array: (5,3,4,2,1,6). Wir sortieren es mit dem Algorithmus der Einfügesortierung.

• Erste Iteration

Schlüssel : A[1] = 3

Binäre Suche: gibt die Position von 3 als Index 0 zurück. Rest der Elemente im sortierten Array nach rechts verschieben.

• Zweite Iteration

Schlüssel: A[2] = 4

Binäre Suche: gibt die Position von 4 als Index 1 zurück. Rest der Elemente im sortierten Array nach rechts verschieben.

• Dritte Iteration

Schlüssel: A[3] = 2

Binäre Suche: gibt die Position von 2 als Index 0 zurück. Rest der Elemente im sortierten Array nach rechts verschieben.

• Vierte Iteration

Schlüssel: A[4] = 1

Binäre Suche: Rückgabe der Position von 1 als Index 0. Rest der Elemente im sortierten Array nach rechts verschieben.

• Fünfte Iteration

Schlüssel: A[5] = 6

Binäre Suche: gibt die Position von 6 als Index 5 zurück. Auf der rechten Seite befinden sich keine Elemente.

Wir erhalten das sortierte Array nach der vierten Iteration - (1 2 3 4 5 6)

Implementierung des binären Sortieralgorithmus

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int a[], int x, int low, int high) {
  if (high <= low) return (x > a[low]) ? (low + 1) : low;

  int mid = (low + high) / 2;

  if (x == a[mid]) return mid + 1;

  if (x > a[mid]) return binarySearch(a, x, mid + 1, high);
  return binarySearch(a, x, low, mid - 1);
}

void binarySort(int a[], int n) {
  for (int i = 1; i < n; ++i) {
    int j = i - 1;
    int key = a[i];
    int pos = binarySearch(a, key, 0, j);
    while (j >= pos) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
}

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  binarySort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Binärer Sortieralgorithmus Komplexität

Zeitkomplexität

• Durchschnittlicher Fall

Die binäre Suche hat eine logarithmische Komplexität logn im Vergleich zur linearen Komplexität n der linearen Suche, die bei der Einfügungssortierung verwendet wird. Wir verwenden binäre Sortierung für n Elemente, was uns die Zeitkomplexität nlogn gibt. Daher ist die Zeitkomplexität in der Größenordnung von [Big Theta]: O(nlogn).

• Schlimmster Fall

Der ungünstigste Fall tritt ein, wenn das Array umgekehrt sortiert ist und die maximale Anzahl von Verschiebungen erforderlich ist. Die Zeitkomplexität im schlimmsten Fall ist [Big O]: O(nlogn).

• Bester Fall

Der beste Fall tritt ein, wenn das Array bereits sortiert ist und keine Verschiebung von Elementen erforderlich ist. Die Zeitkomplexität im besten Fall ist [Big Omega]: O(n).

Raumkomplexität

Die Platzkomplexität für den binären Sortieralgorithmus ist O(n), da außer einer temporären Variablen kein zusätzlicher Speicher benötigt wird.