Shell-Sortierung

Shell-Sort ist eine effiziente verbesserte Version der Insertionssortierung, die 1959 von Donald Shell vorgeschlagen wurde.

Die Kernidee von Shell-Sort istDurch das Unterteilen der ursprünglichen Liste in mehrere Teilfolgen wird zuerst auf jeder Teilfolge eine Insertionssortierung durchgeführt, dann wird der Abstand zwischen den Teilfolgen schrittweise verringert und schließlich eine Standard-Insertionssortierung auf der gesamten Liste durchgeführt.Diese Methode ermöglicht es Elementen, sich über große Spannen zu bewegen, wodurch in den frühen Phasen eine große Anzahl von Inversionen beseitigt und die Sortiereffizienz erheblich verbessert wird.

Stellen Sie sich vor, Sie sortieren ein gemischtes Kartenspiel. Insertionssortierung ist wie das Aufnehmen von Karten eine nach der anderen und das Einfügen jeder Karte an die richtige Position in der bereits sortierten Hand. Shell-Sort hingegen ist wie das Herausziehen alle paar Karten, um einen kleinen Stapel zu bilden und ihn zu sortieren, dann das Verringern des Ziehintervalls und das Wiederholen des Vorgangs. Wenn das Intervall auf 1 verringert wird, wird daraus eine Standard-Insertionssortierung, aber dann ist die gesamte Sequenz bereits im Wesentlichen geordnet, sodass die abschließende Insertionssortierung sehr schnell sein wird.

Funktionsweise

Der Schlüssel zu Shell-Sort liegt in einem sogenanntenInkrementsequenz-Konzept. Die Inkrementsequenz bestimmt jeweils den Abstand zum Unterteilen in Teilfolgen. Der Algorithmus führt mehrere Sortierrunden auf der Liste gemäß einer schrittweise abnehmenden Inkrementsequenz durch.

Algorithmusschritte

  1. Wählen Sie die Inkrementsequenz aus.Bestimmen Sie eine Folge ganzer Zahlen von groß nach klein, wobei das letzte Inkrement 1 sein muss. Das am häufigsten verwendete Anfangsinkrement ist die Hälfte der Array-Länge, und danach wird es jedes Mal halbiert.
  2. Nach Inkrement gruppieren: für das aktuelle Inkrementgap, unterteilen Sie die gesamte Liste ingapTeilfolgen. Jede Teilfolge besteht aus allen Elementen mit einem Abstand vongapDie Elementzusammensetzung.
  3. Insertionssortierung auf den Teilfolgen durchführenFühren Sie auf jeder Teilfolge separat eine Insertionssortierung durch.
  4. Inkrement verringernErmitteln Sie ein neues, kleineres Inkrement, und wiederholen Sie die Schritte 2 und 3.
  5. Abschließende SortierungWenn das Inkrement auf 1 reduziert wird, führe eine Standard-Insertionssortierung für die gesamte Liste durch; zu diesem Zeitpunkt ist die Liste bereits im Wesentlichen geordnet, sodass das Sortieren schnell abgeschlossen wird.

Anwendbarkeit

Die Zeitkomplexität von Shellsort istO(n^(1.3-2)), und die Speicherkomplexität ist von konstanter OrdnungO(1). Shellsort ist nicht so schnell wieO(n(logn)), womit der Quicksort-Algorithmus schnell ist, daher eignet es sich gut für mittlere Größenordnungen, ist aber nicht die optimale Wahl zum Sortieren sehr großer Datenmengen. Kurz gesagt, verglichen mit den gewöhnlichenO(n^2 )Algorithmen mit dieser Zeitkomplexität sind viel schneller.

Prozessdiagramm

Der Zweck von Shellsort ist es, die Insertionssortierung für eine höhere Geschwindigkeit zu verbessern. Es vertauscht nicht benachbarte Elemente, um Teile des Arrays zu sortieren, und verwendet schließlich die Insertionssortierung, um das lokal geordnete Array zu sortieren.

Hier wählen wir das Inkrementgap=length/2, reduzieren das Inkrement aufgap = gap/2Methode, wobei die Sequenz{n/2,(n/2)/2...1}zur Darstellung verwendet wird.

Wie im Beispiel gezeigt:

(1) Der erste Durchlauf mit dem anfänglichen Inkrementgap = length/2 = 4

(2) Der zweite Durchlauf, das Inkrement wird auf 2 reduziert

(3) Der dritte Durchlauf, das Inkrement wird auf 1 reduziert, wodurch das endgültig sortierte Ergebnis erhalten wird

Java-Beispielcode

Quellcode-Paket-Download:Herunterladen

Die innerste Schleife ist tatsächlich Insertionssortierung:

Code der Datei ShellSort.java:

public class ShellSort {
    // Kerncode --- Start
    public static void sort(Comparable[] arr) {
        int j;
        for (int gap = arr.length / 2; gap >  0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                Comparable tmp = arr[i];
                for (j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = tmp;
            }
        }
    }
    // Kerncode --- Ende
    public static void main(String[] args) {

        int N = 2000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 10);
        ShellSort.sort(arr);
        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }
    }
}

Python-Implementierung des Algorithmus

Wir werden Python verwenden, um Shellsort zu implementieren, und die gängigste Inkrement-Einstellung (Shells ursprüngliche Sequenz) übernehmen:gap = n // 2, und fahren fort,gapeine ganzzahlige Division durch 2 durchzuführen, bisgapist 1.

Beispiel

def shell_sort(arr):
    """
Verwende den Shellsort-Algorithmus, um die Liste in aufsteigender Reihenfolge in-place zu sortieren.
   
Parameter:
arr (list): Die zu sortierende Liste.
   
Rückgabe:
list: Die sortierte Liste (in-place geändert, auch zurückgegeben).
    """

    n = len(arr)
    # Setze die anfängliche Inkrementlücke auf die Hälfte der Länge des Arrays
    gap = n // 2
   
    # Schleife, bis gap auf 0 reduziert ist
    while gap > 0:
        # Beginne bei gap und führe für jedes Element eine "Einfügesortierung" durch
        # Hinweis: Hier geht i von gap bis n-1 und iteriert über alle Elemente
        for i in range(gap, n):
            # Speichere arr[i] in einer temporären Variable temp
            temp = arr[i]
            j = i
            # Führe eine Einfügesortierung für die Teilfolge unter dem aktuellen gap durch
            # Wenn das vorhergehende Element in derselben Teilfolge größer als temp ist, verschiebe es nach hinten
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            # temp an der richtigen Position einfügen
            arr[j] = temp
        # Inkrement reduzieren, z. B. gap halbieren
        gap //= 2
   
    return arr

# Testcode
if __name__ == "__main__":
    # Testdaten 1: zufällig gemischte Reihenfolge
    test_array = [8, 3, 5, 1, 4, 2, 7, 6]
    print("Vor dem Sortieren:", test_array)
    sorted_array = shell_sort(test_array.copy()) # copy verwenden, um das ursprüngliche Array nicht zu verändern
    print("Nach dem Sortieren:", sorted_array)
   
    # Testdaten 2: enthält doppelte Elemente
    test_array2 = [5, 2, 9, 5, 2, 3, 5]
    print("\nVor dem Sortieren:", test_array2)
    print("Nach dem Sortieren:", shell_sort(test_array2.copy()))
   
    # Testdaten 3: umgekehrtes Array
    test_array3 = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
    print("\nVor dem Sortieren:", test_array3)
    print("Nach dem Sortieren:", shell_sort(test_array3.copy()))

Codeanalyse:

  1. def shell_sort(arr):Definiere die Shellsort-Funktion.
  2. n = len(arr)Ermittle die Array-Länge.
  3. gap = n // 2Initialisiere das Inkrement. Dies ist der klassischste Startpunkt für die Inkrementfolge bei Shellsort.
  4. while gap > 0:Äußere Schleife, die das Inkrement steuert, sodass es allmählich abnimmt, bis es 0 wird (nachdem es tatsächlich 1 war und die Ausführung beendet hat,gap //= 2wird es 0 und die Schleife endet).
  5. for i in range(gap, n):Innere Schleife. Ausgehend vom IndexgapBeginne zu durchlaufen.izeigt auf das aktuelle Element, das eingefügt werden soll. Beachte: Diese Schleife behandelt geschickt alle Elemente mitgapTeilfolgen mit ... als Intervall.
  6. temp = arr[i]undj = i: den Wert des aktuellen Elements speichern und verwenden,jum die Position zu erfassen, an der es in die aktuelle Teilfolge eingefügt werden soll.
  7. while j >= gap and arr[j - gap] > temp:Dies ist der Kern der Insertionssortierung. Innerhalb derselben Teilfolge (durchj - gapIndexieren, um auf das vorherige Element zuzugreifen), wenn das vorherige Element größer ist alstempwenn es größer ist, das vorherige Element nach hinten verschiebengapPosition.
  8. arr[j] = temp: das gespeichertetempden Wert an der richtigen Position einfügen.
  9. gap //= 2Nach einer Sortierrunde das Inkrement halbieren und die nächste Runde der feineren Sortierung durchführen.
  10. return arr: das sortierte Array zurückgeben.

Auswahl der Inkrementfolge.

Die Wahl der Inkrementfolge wirkt sich direkt auf die Leistung von Shellsort aus. Oben haben wir Shells ursprüngliche Folge verwendet (n/2, n/4, ..., 1), aber sie ist nicht optimal. Nachfolgend sind mehrere gängige Inkrementfolgen aufgeführt:

Name der Folge Erzeugungsformel Eigenschaften und Komplexität.
Ursprüngliche Shell-Folge $gap = \lfloor \frac{n}{2} \rfloor, gap = \lfloor \frac{gap}{2} \rfloor...$ Einfach zu implementieren, mit einer Zeitkomplexität im schlechtesten Fall von $O(n^2)$.
Hibbard-Folge $1, 3, 7, 15, ..., 2^k - 1$ Die Zeitkomplexität im schlechtesten Fall kann auf $O(n^{3/2})$ verbessert werden.
Knuth-Folge $1, 4, 13, 40, ..., (3^k - 1) / 2$ (kleiner als n) Die durchschnittliche Zeitkomplexität beträgt etwa $O(n^{1.25})$, und sie wird in der Praxis häufig verwendet.
Sedgewick-Folge $1, 5, 19, 41, 109, ...$ (eine Mischung aus $9 \times 4^k - 9 \times 2^k + 1$ und $4^k - 3 \times 2^k + 1$) Sie ist eine der bekanntesten Folgen und erreicht im schlechtesten Fall eine Komplexität von $O(n^{4/3})$.

Beispielimplementierung unter Verwendung der Knuth-Folge

Beispiel

def shell_sort_knuth(arr):
    n = len(arr)
    # Knuth-Inkrementfolge generieren: 1, 4, 13, 40, 121, ...
    gap = 1
    while gap < n // 3:
        gap = 3 * gap + 1  # Erzeuge das maximale Anfangsinkrement
   
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 3  # Knuth schlägt vor, jedes Mal durch 3 zu teilen
    return arr

# Teste die Version mit der Knuth-Folge
test_array = [33, 12, 56, 78, 2, 45, 67, 89, 1, 23]
print(Vor dem Sortieren mit der Knuth-Folge:, test_array)
print(Nach dem Sortieren mit der Knuth-Folge:, shell_sort_knuth(test_array.copy()))

Algorithmus-Eigenschaften und Komplexitätsanalyse

Zeitkomplexität

Die Analyse der Zeitkomplexität von Shellsort ist sehr komplex, weil sie von der gewählten Inkrementfolge abhängt.

  • Schlechtester FallBei Verwendung von Shells ursprünglicher Inkrementfolge ist die Zeitkomplexität im schlechtesten Fall $O(n^2)$.
  • Durchschnittlicher Fall: Bei besseren Inkrementfolgen (wie Knuth, Sedgewick) liegt die durchschnittliche Zeitkomplexität zwischen $O(n^{1.25})$ und $O(n^{1.5})$.
  • Bester FallWenn das Array bereits sortiert ist, kann sich die Komplexität $O(n \log n)$ nähern.

Speicherkomplexität

  • Shellsort ist einIn-Place-Sortieralgorithmus, der nur eine konstante Menge zusätzlichen Speicher benötigt (wie z. B.temp, gap, i, jVariablen), sodass die Speicherkomplexität $O(1)$ beträgt.

Stabilität

  • Shellsort ist eininstabilerSortieralgorithmus. Denn beim Sortieren in Gruppen nach Inkrement können gleiche Elemente in verschiedene Teilfolgen gelangen und ihre relative Reihenfolge kann sich durch die Bewegung ändern.

Einfacher Vergleich mit anderen Sortieralgorithmen

Funktionen Shell-Sortierung Insertionssortierung Mergesort Quicksort
Durchschnittliche Zeitkomplexität. $O(n^{1.25})$ ~ $O(n^{1.5})$ $O(n^2)$ $O(n \log n)$ $O(n \log n)$
Speicherkomplexität $O(1)$ $O(1)$ $O(n)$ $O(\log n)$
Stabilität instabil Stabil Stabil instabil
Vorteile Gute Leistung für mittelgroße Datenmengen, In-Place-Sortierung Einfach, effizient für kleine Datenmengen oder nahezu sortierte Daten Stabil, hervorragende Zeitkomplexität Am schnellsten in durchschnittlichen Fällen.
Nachteile Die Komplexitätsanalyse ist schwierig, und die Wahl der Inkrementfolge hat großen Einfluss. Geringe Effizienz bei großen Datenmengen. Erfordert zusätzlichen Speicherplatz. Im schlimmsten Fall degeneriert es zu $O(n^2)$.

Weitere Codebeispiele.

Weitere Erweiterungen