2.5 ShellSort: Verbessertes Sortieren durch Einfügen

Eine Variante des InsertionSort-Algorithmus, die im Allgemeinen schneller ist, nennt sich ShellSort.

2.5.1 Algorithmus

Schauen Sie sich nochmal den InsertionSort-Algorithmus an. Sein Problem ist, dass beim Suchen des Einfügeindex größere Elemente immer nur jeweils um einen Index nach hinten verschoben werden. Wenn sich das kleinste Element zufällig am Ende eines Arrays der Länge n befindet, dann sind n-1 Verschiebeoperationen notwendig, bevor das kleinste Element anschließend ganz vorne einsortiert wird. Die Anzahl dieser Verschiebeoperationen, die beim Transport eines Elementes an seine korrekte Position notwendig sind, werden beim Shellsort-Algorithmus reduziert.

Die Grundidee des ShellSort-Algorithmus ist dabei die, dass der InsertionSort-Algorithmus in mehreren Schritten wiederholt angewendet wird. In einem Schritt werden dabei nicht alle Elemente des Arrays, sondern nur Elemente mit einem bestimmten Abstand d im Array betrachtet und sortiert.

Habe d bspw. den anfänglichen Wert 4. Dann werden die Elemente an den Positionen 0, 4, 8, 12, 16, ... sortiert, ebenso die Elemente an den Positionen 1, 5, 9, 13, 17, ... sowie 2, 6, 10, 14, 18, ... und 3, 7, 11, 15, 19, ... Nach diesem Schritt besteht das Array also im Prinzip aus 4 sortierten Teil-Arrays. Es wird auch 4-sortiert bzw. allgemein d-sortiert genannt.

Im zweiten Schritt wird d verkleinert und die Sortierung wiederholt. Für d=2 werden bspw. die Teil-Arrays mit den Elementen an den Positionen 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, ... und 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, ... sortiert. Anschließend ist das Array 2-sortiert.

Die Verkleinerung von d und die anschließende d-Sortierung wird so lange wiederholt bis d=1 gilt. Im Fall d=1 wird ja der normale InsertionSort-Algorithmus ausgeführt und das Array ist damit sortiert.

Der Klou an diesem Prinzip ist, dass bei großem d kleine Elemente, die sich hinten im Array befinden, über größere Entfernungen - also mit weniger Verschiebeoperationen - nach vorne bewegt werden können.

Für viele Programmieranfänger ist der Shellsort-Algorithmus nicht auf Anhieb verständlich. Aus diesem Grund möchte ich an einem Beispiel eine alternative Beschreibung vorstellen. Zu sortieren sei ein Array mit den Elementen 5 9 2 4 3 1 7 9 8 2 4 3.

Habe d den Anfangswert 4. Dann kann man sich das Array vorstellen als eine 2-dimensionale Matrix mit 4 Spalten:

5 9 2 4 
3 1 7 9 
8 2 4 3

Diese Matrix wird nun spaltenweise mittels des InsertionSort-Algorithmus sortiert und es ergibt sich:

3 1 2 3 
5 2 4 4 
8 9 7 9

Das eigentliche Array ist damit 4-sortiert und hat die Gestalt 3 1 2 3 5 2 4 4 8 9 7 9.

d wird nun im zweiten Schritt auf den Wert 2 gesetzt. Dann kann man sich das Array vorstellen als eine Matrix mit 2 Spalten:

3 1 
2 3 
5 2 
4 4 
8 9 
7 9

Diese Matrix wird wiederum spaltenweise mittels des InsertionSort-Algorithmus sortiert und es ergibt sich:

2 1 
3 2 
4 3 
5 4 
7 9 
8 9

Das eigentliche Array ist damit 2-sortiert und hat die Gestalt 2 1 3 2 4 3 5 4 7 9 8 9.

Im letzten Schritt wird d auf den Wert 1 gesetzt. Die entsprechende Matrix hat nur eine Spalte, die mittels des InsertionSort-Algorithmus sortiert wird. Damit ist die Sortierung abgeschlossen und es ergibt sich das sortierte Array 1 2 2 3 3 4 4 5 7 8 9 9.

Eine Frage, die sich noch stellt, ist die Wahl der Werte von d, auch Distanzfolge genannt. Hierzu gibt es viele Untersuchungen, inwieweit die Laufzeit des ShellSort-Algorithmus durch geeignete Distanzfolgen verbessert werden kann.

Die einfachste Distanzfolge - auch Distanzfolge nach Shell genannt - lautet ..., 64, 32, 16, 8, 4, 2, 1. Sie entspricht also den Zweierpotenzen. Problem dieser Distanzfolge ist, dass Elemente an ungeraden Positionen erst am Schluss mit Elementen an geraden Positionen verglichen werden. Bessere Ergebnisse liefern die Distanzfolge nach Papernov-Stasevich (..., 511, 255, 127, 63, 31, 15, 7, 3, 1) und die Distanzfolge nach Knuth (..., 1093, 364, 121, 40, 13, 4, 1). In allen Fällen wird das anfängliche d auf die größte Zahl der Folge gesetzt, die kleiner als die Länge des zu sortierenden Arrays ist.

Die folgende Klasse ShellSort (ShellSort.ham) implementiert das Interface SortierAlgorithmus entsprechend des ShellSort-Algorithmus:

public class ShellSort implements SortierAlgorithmus {

  // sortiert das uebergebene Array in aufsteigender Reihenfolge
  // gemaess dem ShellSort-Algorithmus
  public void sortiere(int[] zahlen) {
    sortiere(zahlen, new ShellDistanz(zahlen.length));
    //sortiere(zahlen, new PapernovStasevichDistanz(zahlen.length));
    //sortiere(zahlen, new KnuthDistanz(zahlen.length));
  }

  // sortiert das uebergebene Array in aufsteigender Reihenfolge
  // gemaess dem ShellSort-Algorithmus und der uebergebenen Distanz
  public void sortiere(int[] zahlen, Distanz distanzObjekt) {
    int distanz = distanzObjekt.berechneNaechsteDistanz();
    while (distanz > 0) {
      for (int abIndex = 0; abIndex < distanz; abIndex++) {
        insertionSort(zahlen, abIndex, distanz);
      }
      distanz = distanzObjekt.berechneNaechsteDistanz();
    }
  }

  // analog dem InsertionSort-Algorithmus; es werden jedoch nur die
  // Elemente ab "abIndex" beruecksichtigt, die voneinander eine
  // Entfernung "distanz" haben
  public void insertionSort(int[] zahlen, int abIndex, int distanz) {
    // durchlaufe alle Zahlen ab der zweiten
    for (int aktIndex = abIndex+distanz; 
             aktIndex < zahlen.length; 
             aktIndex += distanz) {
      int aktuelleZahl = zahlen[aktIndex];
      int einfuegeIndex =
        sucheEinfuegeIndex(zahlen, aktuelleZahl, aktIndex, distanz);
      zahlen[einfuegeIndex] = aktuelleZahl;
    }
  }

  // sucht und liefert vor der aktuellen Zahl den Index des Arrays, wo 
  // die aktuelle Zahl eingefuegt werden muss, und verschiebt alle
  // größeren Zahlen jeweils um "distanz" Positionen nach hinten im Array
  private int sucheEinfuegeIndex(int[] zahlen, int zahl,
                                   int aktIndex, int distanz) {
    int vergleichsIndex = aktIndex - distanz;
    while (vergleichsIndex >= 0 && zahlen[vergleichsIndex] > zahl) {
      // Zahl im Array um eine Position nach hinten verschieben
      zahlen[vergleichsIndex + distanz] = zahlen[vergleichsIndex];
      vergleichsIndex -= distanz;
    }
    return vergleichsIndex + distanz;
  }

  /* der ShellSort-Algorithmus in kompakter Form
  public void sortiere(int[] zahlen, Distanz distanzObjekt) {
    int distanz = distanzObjekt.berechneNaechsteDistanz();
    while (distanz > 0) {
      for (int abIndex = 0; abIndex < distanz; abIndex++) {
        for (int aktIndex=abIndex+distanz; 
                     aktIndex < zahlen.length; 
                     aktIndex += distanz) {
          int aktuelleZahl = zahlen[aktIndex];
          int vergleichsIndex = aktIndex-distanz;
          while (vergleichsIndex >= 0 && zahlen[vergleichsIndex] > aktuelleZahl) {
            zahlen[vergleichsIndex+distanz] = zahlen[vergleichsIndex];
            vergleichsIndex -= distanz;
          }
          zahlen[vergleichsIndex+distanz] = aktuelleZahl;
        }
      }
      distanz = distanzObjekt.berechneNaechsteDistanz();
    }
  }
  */
}

// Berechnung der ShellSort-Distanz
interface Distanz {
  public int berechneNaechsteDistanz();
}

// Distanz nach D.L. Shell (1959)
class ShellDistanz implements Distanz {

  int distanz;

  ShellDistanz(int arrayLaenge) {
    this.distanz = 1;
    while (this.distanz < arrayLaenge) {
      this.distanz = this.distanz * 2;
    }
  }

  public int berechneNaechsteDistanz() {
    this.distanz = this.distanz / 2;
    return this.distanz;
  }
}

// Distanz nach Papernov-Stasevich (1965)
class PapernovStasevichDistanz implements Distanz {

  int distanz;

  PapernovStasevichDistanz(int arrayLaenge) {
    this.distanz = 1;
    while (this.distanz < arrayLaenge) {
      this.distanz = (this.distanz + 1) * 2 - 1;
    }
  }

  public int berechneNaechsteDistanz() {
    this.distanz = (this.distanz + 1) / 2 - 1;
    return this.distanz;
  }
}

// Distanz nach Knuth
class KnuthDistanz implements Distanz {

  int distanz;

  KnuthDistanz(int arrayLaenge) {
    this.distanz = 1;
    while (this.distanz < arrayLaenge) {
      this.distanz = this.distanz * 3 + 1;
    }
  }

  public int berechneNaechsteDistanz() {
    this.distanz = (this.distanz - 1) / 3;
    return this.distanz;
  }
}

2.5.2 Visualisierendes Hamster-Programm

Die folgende Hamster-Klasse ShellSortHamster (ShellSortHamster.ham) implementiert das Interface SortierHamster und visualisiert dabei den ShellSort-Algorithmus. Voraussetzung ist, dass es im Territorium drei nicht durch Mauern blockierte Reihen unterhalb des Standard-Hamsters gibt. Die Visualisierung erfolgt analog zur Visualisierung des InsertionSort-Algorithmus. Dabei markieren in der zweiten Reihe unterhalb der Körnerhaufenreihe eine Menge von Hamstern die Elemente des aktuell betrachteten Teil-Arrays.

public class ShellSort implements SortierAlgorithmus {

  // sortiert das uebergebene Array in aufsteigender Reihenfolge
  // gemaess dem ShellSort-Algorithmus
  public void sortiere(int[] zahlen) {
    sortiere(zahlen, new ShellDistanz(zahlen.length));
    //sortiere(zahlen, new PapernovStasevichDistanz(zahlen.length));
    //sortiere(zahlen, new KnuthDistanz(zahlen.length));
  }

  // sortiert das uebergebene Array in aufsteigender Reihenfolge
  // gemaess dem ShellSort-Algorithmus und der uebergebenen Distanz
  public void sortiere(int[] zahlen, Distanz distanzObjekt) {
    int distanz = distanzObjekt.berechneNaechsteDistanz();
    while (distanz > 0) {
      for (int abIndex = 0; abIndex < distanz; abIndex++) {
        insertionSort(zahlen, abIndex, distanz);
      }
      distanz = distanzObjekt.berechneNaechsteDistanz();
    }
  }

  // analog dem InsertionSort-Algorithmus; es werden jedoch nur die
  // Elemente ab "abIndex" beruecksichtigt, die voneinander eine
  // Entfernung "distanz" haben
  public void insertionSort(int[] zahlen, int abIndex, int distanz) {
    // durchlaufe alle Zahlen ab der zweiten
    for (int aktIndex = abIndex+distanz; 
             aktIndex < zahlen.length; 
             aktIndex += distanz) {
      int aktuelleZahl = zahlen[aktIndex];
      int einfuegeIndex =
        sucheEinfuegeIndex(zahlen, aktuelleZahl, aktIndex, distanz);
      zahlen[einfuegeIndex] = aktuelleZahl;
    }
  }

  // sucht und liefert vor der aktuellen Zahl den Index des Arrays, wo 
  // die aktuelle Zahl eingefuegt werden muss, und verschiebt alle
  // größeren Zahlen jeweils um "distanz" Positionen nach hinten im Array
  private int sucheEinfuegeIndex(int[] zahlen, int zahl,
                                   int aktIndex, int distanz) {
    int vergleichsIndex = aktIndex - distanz;
    while (vergleichsIndex >= 0 && zahlen[vergleichsIndex] > zahl) {
      // Zahl im Array um eine Position nach hinten verschieben
      zahlen[vergleichsIndex + distanz] = zahlen[vergleichsIndex];
      vergleichsIndex -= distanz;
    }
    return vergleichsIndex + distanz;
  }

  /* der ShellSort-Algorithmus in kompakter Form
  public void sortiere(int[] zahlen, Distanz distanzObjekt) {
    int distanz = distanzObjekt.berechneNaechsteDistanz();
    while (distanz > 0) {
      for (int abIndex = 0; abIndex < distanz; abIndex++) {
        for (int aktIndex=abIndex+distanz; 
                     aktIndex < zahlen.length; 
                     aktIndex += distanz) {
          int aktuelleZahl = zahlen[aktIndex];
          int vergleichsIndex = aktIndex-distanz;
          while (vergleichsIndex >= 0 && zahlen[vergleichsIndex] > aktuelleZahl) {
            zahlen[vergleichsIndex+distanz] = zahlen[vergleichsIndex];
            vergleichsIndex -= distanz;
          }
          zahlen[vergleichsIndex+distanz] = aktuelleZahl;
        }
      }
      distanz = distanzObjekt.berechneNaechsteDistanz();
    }
  }
  */
}

// Berechnung der ShellSort-Distanz
interface Distanz {
  public int berechneNaechsteDistanz();
}

// Distanz nach D.L. Shell (1959)
class ShellDistanz implements Distanz {

  int distanz;

  ShellDistanz(int arrayLaenge) {
    this.distanz = 1;
    while (this.distanz < arrayLaenge) {
      this.distanz = this.distanz * 2;
    }
  }

  public int berechneNaechsteDistanz() {
    this.distanz = this.distanz / 2;
    return this.distanz;
  }
}

// Distanz nach Papernov-Stasevich (1965)
class PapernovStasevichDistanz implements Distanz {

  int distanz;

  PapernovStasevichDistanz(int arrayLaenge) {
    this.distanz = 1;
    while (this.distanz < arrayLaenge) {
      this.distanz = (this.distanz + 1) * 2 - 1;
    }
  }

  public int berechneNaechsteDistanz() {
    this.distanz = (this.distanz + 1) / 2 - 1;
    return this.distanz;
  }
}

// Distanz nach Knuth
class KnuthDistanz implements Distanz {

  int distanz;

  KnuthDistanz(int arrayLaenge) {
    this.distanz = 1;
    while (this.distanz < arrayLaenge) {
      this.distanz = this.distanz * 3 + 1;
    }
  }

  public int berechneNaechsteDistanz() {
    this.distanz = (this.distanz - 1) / 3;
    return this.distanz;
  }
}

Mit dem folgendem objektorientierten Hamster-Programm (SortierenMitShellSort) (SortierenMitShellSort.ham) können Sie sich von den Hamstern den ShellSort-Algorithmus demonstrieren lassen.

void main() {
  Hamster paul = Hamster.getStandardHamster();
  String antwort =
    Hamster.getStandardHamster().liesZeichenkette(
      "Moechten Sie textuelle Erlaeuterungen (ja/nein)?");
  SortierHamster sortierer = new ShellSortHamster(antwort.equals("ja"));
  sortierer.sortiereKoernerHaufen();
}

2.5.3 Analyse des Algorithmus

Der ShellSort-Algorithmus ist nicht stabil. ShellSort arbeitet in-place.

Eine Analyse des ShellSort-Algorithmus ist schwierig und hängt natürlich auch von der gewählten Distanzfolge ab. Es kann gezeigt werden, dass für eine Vielzahl von Distanzfolgen die Anzahl an Vergleichen zwischen den Array-Elementen im unglücklichsten Fall $\approx$ $n^{1.5}$ beträgt. n ist dabei die Anzahl an zu sortierenden Elementen.

Im Web finden sich zahlreiche weitere Informationen zum ShellSort-Algorithmus, z.B. unter

• http://de.wikipedia.org/wiki/Shellsort
• http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shell.htm
• http://www.sortieralgorithmen.de/shellsort/index.html