WikiDer > Shellsort
Muschelsortierung (oder Muschelsortierung) ist ein Sortieralgorithmus erfunden 1959 bis 1959 Donald L. Shell.
Es ist ein Fasten Algorithmus das ist auch einfach umzusetzen.
Operation
Shell sort ist eigentlich eine erweiterte Version von Sortieren durch Einfügen. Wenn wir dies analysieren, sehen wir, dass es sich um einen Algorithmus handelt, der schnell sortieren kann, wenn die Daten fast sortiert sind, aber dass er bei völlig unsortierten Daten langsam arbeitet. Daher stellt Shell-Sort sicher, dass die Daten bereits teilweise sortiert sind.
Shell sort teilt die Daten in kleine Stücke, sortiert diese Stücke mit Sortieren durch Einfügen und ordnet alles so an, dass die ersten Elemente aller Stücke an erster Stelle stehen, gefolgt von den zweitplatzierten Elementen in allen Stücken und so weiter. Nach dieser Muschelsortierung beginnt wieder, aber jetzt werden größere Stücke genommen. Am Ende bleibt nur 1 Stück und wenn dieses sortiert ist, ist alles fertig.
Wenn Sie dies lokal in einer Tabelle tun, haben Sie immer eine Tabelle, in der sich alle Elemente befinden, die sich in einem Abstand befinden k sind voneinander sortiert (eine solche Tabelle heißt a k-sortierte Tabelle), wobei k durchläuft eine Reihe von absteigenden Inkrementen. Deshalb war Shell Sort früher abnehmende Inkrementsortierung erwähnt.
Die Wahl der Inkremente beeinflusst die Sortiergeschwindigkeit. Es ist nicht bekannt, was die optimale Reihe ist. Dies zu analysieren wäre sehr schwierig.
Beispiel
Angenommen, wir müssen die folgenden Zahlen von der kleinsten zur größten sortieren:
5 2 9 8 2 3 3 8 5 8 5 1 0 1 7 3 0 6 1 6 8 4 7 7 2
Wir beginnen damit, die Daten neu zu schreiben, aber alle 9 Ziffern beginnen wir in einer neuen Zeile:
5 2 9 8 2 3 3 8 58 5 1 0 1 7 3 0 61 6 8 4 7 7 2
Die 9 Spalten mit 3 (oder 2) Elementen sind die Teile, die wir mit Insertion sortieren werden. Wenn dies erledigt ist, erhalten wir dies als Ergebnis:
1 2 1 0 1 3 2 0 55 5 8 4 2 7 3 8 68 6 9 8 7 7 3
Wenn wir die Daten nun einfach wieder zusammensetzen, stellen wir fest, dass die großen Zahlen meist hinten liegen und die Daten somit schon teilweise sortiert sind:
1 2 1 0 1 3 2 0 5 5 5 8 4 2 7 3 8 6 8 6 9 8 7 7 3
Jetzt fangen wir wieder an, aber jetzt nehmen wir nur 4 Spalten statt 9:
1 2 1 0 1 2 1 01 3 2 0 1 2 2 05 5 5 8 3 3 5 34 2 7 3 => 4 5 7 68 6 8 6 5 6 7 79 8 7 7 8 8 8 83 9
Wenn wir nun die Daten hintereinander platzieren, sehen wir, dass sie fast perfekt sortiert sind:
1 2 1 0 1 2 2 0 3 3 5 3 4 5 7 6 5 6 7 7 8 8 8 8 9
Jetzt sortieren wir einfach den Rest der Daten mit Insertionsort und erhalten:
0 0 1 1 1 2 2 2 3 3 3 4 5 5 5 6 6 7 7 7 8 8 8 8 9
Implementierung
Hier ist ein Beispiel für eine Implementierung in C,die "shellsort"-Funktion sortiert die Array "input" mit "length" Anzahl der Elemente nach dem Shellsort-Algorithmus, zuerst werden die Daten in "length/3"-Spalten aufgeteilt und in den folgenden Schritten wird 1/3 der Spaltenanzahl aus dem vorherigen Schritt verwendet,
LeereMuschelsortierung(intEingang[],intLänge){intich,ja,t,kol;// Beginnen Sie mit der Aufteilung in Länge / 3 Spalten und teilen Sie die Zahl jedes Mal durch 3zum(kol=Länge/3;;kol/=3){wenn(kol==0)kol=1;// jedes Mal eine Spalte nehmenzum(ich=kol;ich<Länge;ich){ja=0;// sortiere die Spalte mit Einfügungssortierungwährend(ich-ja>=kol&&Eingang[ich-ja]<Eingang[ich-kol-ja]){t=Eingang[ich-ja];Eingang[ich-ja]=Eingang[ich-kol-ja];Eingang[ich-kol-ja]=t;ja =kol;}}wenn(kol==1)Rückkehr;}}Diese Implementierung ist einfach, aber ineffizient z.B. Länge = 243, 729, 2187, ... , 3nein(Komplexitätsgrad Auf2)).
Die nächste Implementierung in Java nimmt die Anzahl der Spalten aus einer gut gewählten Sequenz (Array Säulen) sortiert die Spalten mit einer effizienteren Implementierung der Einfügungssortierung.
LeereMuschelsortierung(int[]Eingang,intLänge){intich,ja,k,t,kol;int[]Säulen={1,4,9,29,97,259,815,1968,4711,11969,27901,84801,213331,543749,1355339,3501671,8810089,21521774,58548857,157840433,410151271,1131376761,2147483647};// finde die größte Anzahl von Spalten kleiner als 'Länge'zum(k=0;Säulen[k]<Länge;k);während(--k>=0){kol=Säulen[k];// Sortiere die Spalten mit Einfügungssortierungzum(ich=kol;ich<Länge;ich){t=Eingang[ich];ja=ich;während(ja>=kol&&t<Eingang[ja-kol]){Eingang[ja]=Eingang[ja-kol];ja=ja-kol;}Eingang[ja]=t;}}}