Shellsort, auch bekannt als Sorte von Shell oder die Methode von Shell, ist eine Vergleich-Sorte im Platz. Es verallgemeinert eine wert seiende Sorte, wie Einfügung oder Luftblase-Sorte, durch das Starten des Vergleichs und Austausches von Elementen mit Elementen, die weit einzeln mit benachbarten Elementen vorher fertig sind. Wenn sie mit dem weiten einzeln anfangen, können Elemente einige fehl am Platz Elemente in die Position schneller bewegen als ein einfacher nächster Nachbaraustausch. Donald Shell hat die erste Version dieser Sorte 1959 veröffentlicht. Die Laufzeit von Shellsort ist von der Lücke-Folge schwer abhängig, die es verwendet. Für viele praktische Varianten, ihre Zeitkompliziertheit bestimmend, bleibt ein offenes Problem.

Beschreibung

Shellsort ist ein Mehrpass-Algorithmus. Jeder Pass ist eine Einfügungssorte der Folgen, die aus jedem h-th Element für eine feste Lücke h (auch bekannt als die Zunahme) bestehen. Das wird H-Sortieren genannt.

Ein Beispiel-Lauf von Shellsort mit Lücken 5, 3 und 1 wird unten gezeigt.

\begin {Reihe} {rcccccccccccc }\

&a_1&a_2&a_3&a_4&a_5&a_6&a_7&a_8&a_9&a_ {10} &a_ {11} &a_ {12 }\\\

\hbox {geben data: }\ein

& 62& 83& 18& 53& 07& 17& 95& 86& 47& 69& 25& 28 \\

\hbox {nachdem 5-sorting: }\

& 17& 28& 18& 47& 07& 25& 83& 86& 53& 69& 62& 95 \\

\hbox {nachdem 3-sorting: }\

& 17& 07& 18& 47& 28& 25& 69& 62& 53& 83& 86& 95 \\

\hbox {nachdem 1-sorting: }\

& 07& 17& 18& 25& 28& 47& 53& 62& 69& 83& 86& 95 \\

\end {ordnen }\

</Mathematik>

Der erste Pass, 5-Sortieren-, führt Einfügungssorte auf der getrennten Subreihe (a, a, a), (a, a, a), (a, a), (a, a), (a, a) durch. Zum Beispiel ändert es die Subreihe (a, a, a) von (62, 17, 25) zu (17, 25, 62). Der folgende Pass, 3-Sortieren-, führt Einfügungssorte auf der Subreihe (a, a, a, a), (a, a, a, a), (a, a, a, a) durch. Der letzte Pass, 1 Sortieren, ist eine gewöhnliche Einfügungssorte der kompletten Reihe (a..., a).

Da das Beispiel illustriert, ist die Subreihe, auf der Shellsort funktioniert, am Anfang kurz; später sind sie länger, aber fast bestellt. In beiden Fällen arbeitet Einfügungssorte effizient.

Shellsort ist nicht stabil: Es kann die Verhältnisordnung von Elementen mit gleichen Werten ändern. Es hat "natürliches" Verhalten, in dem es schneller durchführt, wenn der Eingang teilweise sortiert wird.

Pseudocode

Das Verwenden der Lücke-Folge von Marcin Ciura, mit einer inneren Einfügungssorte.

1. Sortieren Sie eine Reihe [0... n-1].

Lücken = [701, 301, 132, 57, 23, 10, 4, 1]

foreach (Lücke in Lücken)

# Tun eine Einfügungssorte für jede Lücke-Größe.

für (ich = Lücke; ich

[j] = [j - Lücke]

[j] = Zeitsekretärin

</Quelle>

Lücke-Folgen

Jede Lücke-Folge, die 1 Erträge eine richtige Sorte enthält; jedoch können die Eigenschaften von so erhaltenen Versionen von Shellsort sehr verschieden sein.

Der Tisch vergleicht unten am meisten vorgeschlagene Lücke-Folgen veröffentlicht bis jetzt. Einige von ihnen haben abnehmende Elemente, die von der Größe der sortierten Reihe (N) abhängen. Andere vergrößern unendliche Folgen, deren Elemente weniger als N in umgekehrter Reihenfolge verwendet werden sollten.

:

Wenn die binäre Darstellung von N viele aufeinander folgende zeroes, das Verwenden von Shellsort enthält, macht die ursprüngliche Lücke-Folge von Shell Θ (N) Vergleiche im Grenzfall. Zum Beispiel kommt dieser Fall für den N vor, der einer Macht zwei gleich ist, wenn Elemente, die größer und kleiner sind als die Mittellinie, gerade und ungerade Positionen beziehungsweise besetzen, da sie nur im letzten Pass verglichen werden.

Obwohl es höhere Kompliziertheit hat als der O (NlogN), der zum Vergleich Sorten optimal ist, leiht die Version von Pratt sich zum Sortieren von Netzen und hat dieselbe asymptotische Tor-Kompliziertheit wie der bitonic Sortierer von Batcher.

Gonnet und Baeza-Yates haben bemerkt, dass Shellsort wenigste Vergleiche durchschnittlich macht, wenn die Verhältnisse von aufeinander folgenden Lücken 2.2 grob gleich sind. Das ist, warum sich ihre Folge mit dem Verhältnis 2.2 und die Folge von Tokuda mit dem Verhältnis 2.25 effizient erweisen. Jedoch ist es nicht bekannt, warum das so ist. Sedgewick empfiehlt, Lücken zu verwenden, die niedrige größte allgemeine Teiler haben oder pairwise coprime sind.

In Bezug auf die durchschnittliche Zahl von Vergleichen sind die am besten bekannten Lücke-Folgen 1, 4, 10, 23, 57, 132, 301, 701 und ähnlich, mit Lücken gefunden experimentell. Optimale Lücken darüber hinaus 701 bleiben unbekannt, aber gute Ergebnisse können durch das Verlängern der obengenannten Folge gemäß der rekursiven Formel erhalten werden.

Die Folge von Tokuda, die durch die einfache Formel definiert ist, wo für praktische Anwendungen empfohlen werden kann.

Rechenbetonte Kompliziertheit

Das folgende Eigentum hält: Nach dem H-Sortieren jeder H-Sorted-Reihe bleibt die Reihe h-sorted. Jede h-sorted- und H-Sorted-Reihe ist auch (ah+ah) - sortiert, für irgendwelche natürlichen Zahlen a und a. Die Grenzfall-Kompliziertheit von Shellsort wird deshalb mit dem Problem von Frobenius verbunden: Für gegebene ganze Zahlen h..., h mit gcd = 1, ist Frobenius Nummer g (h..., h) die größte ganze Zahl, die als ah +... +ah mit der natürlichen Zahl a..., a nicht vertreten werden kann. Mit bekannten Formeln für Zahlen von Frobenius können wir die Grenzfall-Kompliziertheit von Shellsort für mehrere Klassen von Lücke-Folgen bestimmen. Bewiesene Ergebnisse werden im obengenannten Tisch gezeigt.

In Bezug auf die durchschnittliche Zahl von Operationen betrifft keines von bewiesenen Ergebnissen eine praktische Lücke-Folge. Für Lücken, die Mächte zwei sind, hat Espelid diesen Durchschnitt als geschätzt. Knuth hat die durchschnittliche Kompliziertheit bestimmt, eine N-Element-Reihe mit zwei Lücken (h, 1) zu sortieren, um zu sein. Hieraus folgt dass Zwei-Pässe-Shellsort mit h = Θ (N) durchschnittlich O (N) Vergleiche macht. Yao hat die durchschnittliche Kompliziertheit von Drei-Pässe-Shellsort gefunden. Sein Ergebnis wurde von Janson und Knuth raffiniert: Die durchschnittliche Zahl von Vergleichen hat während Shellsort mit drei Lücken gemacht (ch, Cg, 1), wo h und g coprime sind, ist im ersten Pass im zweiten Pass und im dritten Pass. ψ (h, g) in der letzten Formel ist eine komplizierte Funktion, die asymptotisch dem gleich ist. Insbesondere wenn h = Θ (N) und g = Θ (h), die durchschnittliche Zeit des Sortierens O (N) ist.

Gestützt auf Experimenten wird es vermutet, dass Shellsort mit den Lücke-Folgen von Hibbard und Knuths in O (N) durchschnittliche Zeit führt, und dass Gonnets Folge und Baeza-Yates durchschnittlich 0.41NlnN (ln lnN+1/6) Element-Bewegungen verlangt. Annäherungen der durchschnittlichen Zahl von für andere Folgen früher vorgebrachten Operationen scheitern, wenn sortierte Reihe Millionen von Elementen enthält.

Der Graph zeigt unten die durchschnittliche Zahl von Element-Vergleichen in verschiedenen Varianten von Shellsort, der durch das theoretische tiefer geteilt ist, gebunden, d. h. logN!, wo die Folge 1, 4, 10, 23, 57, 132, 301, 701 gemäß der Formel erweitert worden ist.

Die Theorie der Kompliziertheit von Kolmogorov anwendend, haben Jiang, Li und Vitányi die folgenden niedrigeren Grenzen für die Ordnung der durchschnittlichen Zahl von Operationen in einer M Pass Shellsort bewiesen: Ω (mN) wenn mlogN und Ω (mN) wenn m> logN. Deshalb hat Shellsort Aussichten des Laufens in einer durchschnittlichen Zeit, dass asymptotisch wie NlogN wächst, wenn nur man Lücke-Folgen verwendet, deren Zahl von Lücken im Verhältnis zum Logarithmus der Reihe-Größe wächst. Es ist jedoch, unbekannt, ob Shellsort diese asymptotische Ordnung der Kompliziertheit des durchschnittlichen Falls erreichen kann, die zum Vergleich Sorten optimal ist.

Die Grenzfall-Kompliziertheit jeder Version von Shellsort ist von der höheren Ordnung: Plaxton, Poonen und Suel haben gezeigt, dass es mindestens so schnell wächst wie Ω (N (logN/log logN)).

Anwendungen

Shellsort wird jetzt in ernsten Anwendungen selten verwendet. Es führt mehr Operationen durch und hat höheres geheimes Lager Fräulein-Verhältnis als Schnellsortierung. Jedoch, da es relativ kurzen Code braucht und den Anruf-Stapel nicht verwendet, verwenden einige Durchführungen der Qsort-Funktion in der C an eingebetteten Systemen ins Visier genommenen Standardbibliothek es statt der Schnellsortierung. Shellsort wird zum Beispiel in der uClibc Bibliothek verwendet. Aus ähnlichen Gründen ist eine Durchführung von Shellsort im Kern von Linux da.

Shellsort kann auch als ein Subalgorithmus der introspektiven Sorte dienen, um kurze Subreihe zu sortieren und eine pathologische Verlangsamung zu verhindern, wenn die recursion Tiefe eine vorgeschriebene Grenze überschreitet. Dieser Grundsatz wird zum Beispiel im bzip2 Kompressor verwendet.

Siehe auch

• Kamm-Sorte

Bibliografie

• Analyse von Shellsort und Related Algorithms, Robert Sedgewick, dem Vierten europäischen Symposium auf Algorithmen, Barcelona, September 1996.

Außenverbindungen

• Shellsort mit Lücken 5, 3, 1 als ungarische Leute tanzen