Shell-Sortierung

1. Shell-Sortieralgorithmus
2. Shell-Sortierbeispiel
3. Shell-Sort-Algorithmus Implementierung
4. Shell-Sortieralgorithmus Komplexität

Shell sort ist ein hocheffizienter vergleichsbasierter Sortieralgorithmus. Er wird als Verallgemeinerung des Bubble-Sort-Algorithmus oder als optimierter Insertion-Sort-Algorithmus angesehen. Beim Insertion-Sort-Algorithmus werden die Elemente um eine Position weitergeschoben. Im Falle der Shell-Sortierung verschieben wir die Elemente jedoch um h Positionen nach vorne. Der Algorithmus beginnt mit der Sortierung von sehr weit entfernten Elementen und verringert den Abstand schrittweise anhand einer Sequenz, um das gesamte Array zu sortieren. Einige der verwendeten Sequenzen sind:

Shell-Sortieralgorithmus

Nehmen wir an, dass wir ein unsortiertes Array A[] mit n Elementen haben. Wir werden die ursprüngliche Reihenfolge der Shell verwenden, um das Array zu sortieren.

Shell-Sortierbeispiel

Angenommen, wir haben das Array: (9, 8, 3, 7, 5, 6, 4, 1). Wir werden es mit dem Shell-Sortieralgorithmus sortieren und die ursprüngliche Reihenfolge der Shell verwenden, um die Lückenintervalle zu reduzieren.

• Erste Iteration

n/2 = 4 , Elemente, die im Intervall 4 liegen, werden verglichen und getauscht.

A[0] > A[4] → vertauscht, (5,8,3,7,9,6,4,1).

A[1] > A[5] → vertauscht, (5,6,3,7,9,8,4,1).

A[2] < A[6]

A[3] > A[7] → vertauscht, (5,6,3,1,9,8,4,7).

Das Array wird zu: (5,6,3,1,9,8,4,7).

• Zweite Iteration

n/4 = 2 , Elemente, die im Intervall 2 liegen, werden verglichen und getauscht.

A[0] > A[2] → vertauscht, (3,6,5,1,9,8,4,7).

A[1] > A[3] → vertauscht, (3,1,5,6,9,8,4,7).

A[0] < A[2] < A[4]

A[1] < A[3] < A[5]

A[2] > A[4] und A[4] > A[6] → vertauscht, (3,1,4,6,5,8,9,7).

A[1] < A[3] < A[5] aber A[5] > A[7] → vertauscht, (3,1,4,6,5,7,9,8).

Das Array wird zu: (3,1,4,6,5,7,9,8).

• Dritte Iteration

n/8 = 1 , Elemente, die im Intervall 1 liegen, werden verglichen und getauscht.

A[0] > A[1] → vertauscht, (1,3,4,6,5,7,9,8).

A[0] .. A[2] → sortiert

A[0] .. A[3] → sortiert

A[0] .. A[3] → sortiert, aber A[3] > A[4] → vertauscht, (1,3,4,5,6,7,9,8).

A[0] .. A[5] → sortiert

A[0] .. A[6] → sortiert

A[0] .. A[6] → sortiert, aber A[6] > A[7] → vertauscht, (1, 3, 4, 5, 6, 7, 8, 9).

Shell-Sort-Algorithmus Implementierung

#include <bits/stdc++.h>
using namespace std;
void shellSort(int arr[], int n) {
  for (int gap = n / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < n; i += 1) {
      int temp = arr[i];
      int j;
      for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
        arr[j] = arr[j - gap];
      arr[j] = temp;
    }
  }
}
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";
  shellSort(arr, n);  // Sort elements in ascending order
  cout << "Output arr: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Shell-Sortieralgorithmus Komplexität

Zeitkomplexität

• Durchschnittlicher Fall

Die Komplexität hängt von der für die Sortierung gewählten Reihenfolge ab. Die Zeitkomplexität liegt in der Größenordnung von [Big Theta]: O(nlog(n)²).

• Schlimmster Fall

Die Worst-Case-Zeitkomplexität für Shell Sort ist immer kleiner als gleich O(n²). Genauer gesagt ist sie nach dem Satz von Poonen gegeben durch Θ(nlogn)²/(log log n)²) oder Θ(nlog n)²/log log n) oder Θ(n(log n)²) oder etwas dazwischen. Die Zeitkomplexität im schlimmsten Fall ist [Big O]: weniger als gleich O(n²).

• Bester Fall

Der Best-Case tritt auf, wenn das Array bereits sortiert ist und die für jedes Intervall erforderlichen Vergleiche gleich der Größe des Arrays sind. Die Zeitkomplexität im besten Fall ist [Big Omega]: O(nlogn).

Raumkomplexität

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