Shellsort
aus Wikipedia, der freien Enzyklopädie
 |
Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf bitte mit, ihn zu verbessern, und entferne anschließend diese Markierung. |
Shellsort ist ein von Donald L. Shell im Jahre 1959 entwickeltes Sortierverfahren, das auf dem Sortierverfahren des direkten Einfügens (Insertionsort) basiert.
Inhaltsverzeichnis |
[Bearbeiten] Prinzip
Shellsort bedient sich prinzipiell Insertionsort. Es versucht den Nachteil auszugleichen, dass hier Elemente in der Sequenz oft über weite Strecken verschoben werden müssen. Dies macht Insertionsort ineffizient. Shellsort verfolgt den Ansatz, dass die Sequenz z.B. erst 4-sortiert wird, dann 2-sortiert, und zuletzt mit normalem Insertionsort sozusagen 1-sortiert.
Anschaulich wäre dies anhand von Hilfsmatrizen darzustellen (siehe Beispiel):
- Die Daten werden in eine k-spaltige Matrix geschrieben
- Die Spalten der Matrix werden einzeln sortiert
Daraus resultiert eine grobe Sortierung. Dieser Schritt wird mehrmals wiederholt, wobei jeweils die Breite der Matrix verringert wird, bis die Matrix nur noch aus einer einzigen vollständig sortierten Spalte besteht.
Shellsort arbeitet in-place, gehört jedoch nicht zu den stabilen Sortieralgorithmen.
[Bearbeiten] Beispiel
Zu sortieren sind die Zahlen "2 5 3 4 3 9 3 2 5 4 1 3" mittels der Folge 2n,...,4,2,1.
Zuerst werden die Daten in eine Matrix mit 4 Spalten eingetragen und spaltenweise sortiert. Die Zahlenfolge wird also 4-sortiert.
2 5 3 4 2 4 1 2 3 9 3 2 -> 3 5 3 3 5 4 1 3 5 9 3 4
Die sortierte 4-Spalten-Matrix wird nun in zwei Spalten aufgeteilt. Diese Spalten werden nun 2-sortiert.
2 1 2 1 3 3 3 2 5 3 -> 4 3 4 2 5 3 5 3 5 3 9 4 9 4
Die sortierte 2-Spalten-Matrix wird nun in eine Spalte geschrieben und wieder sortiert mittels normalem Insertionsort. Der Vorteil dabei besteht darin, dass kein Element der Sequenz so weit verschoben werden muss, wie bei Insertionsort, das auf eine völlig unsortierte Folge losgelassen wird.
2 3 4 5 5 9 1 2 3 3 3 4 -> 1 2 2 3 3 3 3 4 4 5 5 9
Die hier verwendete Schrittfolge 1,2,4,8,16,...,2n (wie es 1959 original von Shell vorgeschlagen wurde) erweist sich in der Praxis allerdings als nicht zweckmäßig, da nur gerade Stellen sortiert werden und ungerade Stellen der Sequenz nur im letzten Schritt angefasst werden. Als zweckmäßiger hat sich 1,4,13, ... 3(n-1)+1 erwiesen.
[Bearbeiten] Implementierung
[Bearbeiten] Java 5
Shell sort ist eine Verbesserung des Algorithmus straight insertion. Dort wandern nämlich die Elemente in Einzelschritten auf ihren Platz: Nach dem Finden des kleinsten Elements werden die dazwischenliegenden einzeln hochgeschoben und nur das kleinste „springt“. Die meisten (d.h. n) Elemente werden von ihrem ursprünglichen Platz in durchschnittlich n/3 Schritten zu ihrem endgültigen Platz geschoben.
Beim Shell-Sort führt man abnehmende Schrittweiten k[1], k[2], … k[t] ein, wobei die letzte Schrittweite immer k[t] = 1 ist. Es werden nacheinander t Schritte durchgeführt; im m-ten Schritt springen die Elemente in Richtung ihres zukünftigen Platzes um jeweils k[m] Stellen. Im ersten Schritt werden diejenigen Elemente untereinander sortiert, die k[1] Stellen voneinander entfernt sind; dann diejenigen, die eine Entfernung k[2] voneinander haben usw. Der Effekt dieser Vorgehensweise ist es, dass die Elemente im ersten Durchgang nicht um einen, sondern um k[1] Stellen zu ihrem Platz „springen“.
Die letzte Schrittweite k[t] ist 1, d.h. zum Schluss wird ein ganz normaler Sortiervorgang straight insertion durchgeführt. Dies garantiert, dass am Ende die Reihung sortiert ist. Der Algorithmus braucht jedoch kaum noch etwas zu tun, da die vorherigen Schritte die Reihung schon fast vollständig sortiert haben.
Durch die geeignete Wahl der Schrittweiten k[1], k[2], … k[t] kann der Sortieraufwand deutlich reduziert werden. Für die Schrittweiten (1, 3, 7, 15, 31, … ) wurde nachgewiesen (s. Donald E. Knuth: The Art of Computer Programming), dass die Zeitkomplexität des Algorithmus n hoch 1,2 beträgt, was deutlich besser ist, als die quadratische Komplexität von Bubblesort, Insertionsort oder Selectionsort, jedoch (zumindest für sehr große Datenmengen) schlechter als die Komplexität n log n von Quicksort oder Heapsort.
static <E extends Comparable<E>> void shellSort(E[] sammlung, final int[] schrittweiten) {
for (int schrittweite : schrittweiten) { // straight insertion mit schrittweite
for (int index = schrittweite; index < sammlung.length; index++){
E elementZumEinfuegen = sammlung[index];
int einfuegestelle = index;
while (einfuegestelle - schrittweite >= 0 &&
elementZumEinfuegen.compareTo(sammlung[einfuegestelle-schrittweite]) < 0) {
sammlung[einfuegestelle] = sammlung[einfuegestelle - schrittweite];
einfuegestelle -= schrittweite; // Sprung um schrittweite
}
sammlung[einfuegestelle] = elementZumEinfuegen;
}
}
}
[Bearbeiten] Java
Tatsächlich werden die Daten nicht in Form einer Matrix, sondern in Form eines eindimensionalen Feldes angeordnet. Die Spalten werden durch geschickte Indizierung gebildet. So bilden alle Elemente im Abstand h eine Spalte. Die Spalten werden per Insertionsort sortiert, da dieser Algorithmus von einer Vorsortierung der Daten profitieren kann.
In folgendem Programm werden die Daten zuerst in h=2147483647 Spalten angeordnet, sofern so viele Daten vorhanden sind. Wenn nicht, wird die for-i-Schleife übersprungen und mit h=1131376761 fortgefahren usw.
void shellsort (int[] a, int n) { int i, j, k, h, t; int[] spalten = {2147483647, 1131376761, 410151271, 157840433, 58548857, 21521774, 8810089, 3501671, 1355339, 543749, 213331, 84801, 27901, 11969, 4711, 1968, 815, 271, 111, 41, 13, 4, 1}; for (k=0; k<23; k++) { h=spalten[k]; // Sortiere die "Spalten" mit Insertionsort for (i=h; i<n; i++) { t=a[i]; j=i; while (j>=h && a[j-h]>t) { a[j]=a[j-h]; j=j-h; } a[j]=t; } } }
[Bearbeiten] C
Ein Array wird sortiert und vorher und nachher ausgegeben.
#include <stdio.h> inline void tausche(int *a, int *b) { int c = *a; *a = *b; *b = c; } void sort(int array[], size_t size) { int step=size -1; int start,i,j; do{ step/=2; for(start=0;start<step;++start){ for(i=start+1;i<size;i+=step){ for(j=i-1;j>=0;j-=step){ if((j+step)<size && array[j]>array[j+step]) tausche(&array[j],&array[j+step]); else break; } } } }while(step>0); } int main(void){ int n = 0; int x[] = {30,5,24,11,26,20,4,23,9,25,6,28,15,27,7,22,10,3,1,13,21,29,17,2,19,8,16,14,12,18}; printf("Shellsort...\nVorher: "); for (n = 0;n < sizeof(x)/sizeof(int);n++) printf("%d|",x[n]); sort(x,sizeof(x)/sizeof(int)); printf("\n\nNachher:"); for (n = 0;n < sizeof(x)/sizeof(int);n++) printf("%d|",x[n]); return 0; }
[Bearbeiten] Python
def shellSort(items):
inc = len(items) / 2
while inc:
for i in xrange(len(items)):
j = i
temp = items[i]
while j >= inc and items[j-inc] > temp:
items[j] = items[j - inc]
j -= inc
items[j] = temp
inc = inc/2 if inc/2 else (0 if inc==1 else 1)
a = [35, -8, 11, 1, 68, 0, 3];
shellSort(a)
print a # [-8, 0, 1, 3, 11, 35, 68]
[Bearbeiten] Komplexität
Die Komplexität von Shellsort hängt von der Wahl der Folge für die Spaltenanzahl h ab. Mit der Folge 1, 3, 7, 15, 31, 63, ..., 2k - 1 wird eine Komplexität von O(n1,5) erreicht. Mit der Folge 1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2p3q ist die Komplexität O(n·log(n)2). Es wurde experimentell belegt, dass die allgemeine Komplexität höchstwahrscheinlich in O(n1.25) liegt. Eine Folge für O(n·log(n)) scheint jedoch nicht zu existieren.
Die Suche nach einer optimalen Folge, gestaltet sich dabei als äußerst schwierig. Zu große Abstände zwischen den Folgegliedern ergeben zu große Verschiebungen, zu enge Abstände bewirken zu viele Durchläufe bis zur letztendlichen Sortierung. Dabei gilt es bei der Wahl einer Folge zu vermeiden, dass sie gemeinsame Teiler haben, da eine a*b-sortierte Folge auch a-sortiert und b-sortiert ist, sodass es dann zu unnützen Sortierschritt käme.
[Bearbeiten] Variationen
Combsort arbeitet ähnlich wie Shellsort. Dabei wird die Spaltensortierung nur mit einem Durchlauf von Bubblesort sortiert, bevor die Spaltenanzahl verringert wird.
[Bearbeiten] Literatur
- Donald L. Shell: A High-Speed Sorting Procedure. Commun. ACM 2(7): 30-32 (1959).
- Robert Sedgewick: Algorithms in Java, Part 1-4 Addison-Wesley, ISBN 0201361205
[Bearbeiten] Weblinks
