Kamm-Sorte ist ein relativ vereinfachter Sortieren-Algorithmus, der ursprünglich durch Włodzimierz Dobosiewicz 1980 entworfen ist. Später wurde es wieder entdeckt und von Stephen Lacey und Richard Box mit einem Artikel Byte Magazine veröffentlicht im April 1991 verbreitet. Kamm-Sorte übertrifft Luftblase-Sorte und Rivale-Algorithmen wie Schnellsortierung (Sehvergleich). Die Grundidee ist, Schildkröten oder kleine Werte in der Nähe vom Ende der Liste zu beseitigen, da in einer Luftblase sortieren, verlangsamen diese das Sortieren schrecklich. (Kaninchen, große Werte um den Anfang der Liste, werfen kein Problem in der Luftblase-Sorte auf.).

In der Luftblase-Sorte, wenn irgendwelche zwei Elemente verglichen werden, haben sie immer eine Lücke (Entfernung von einander) von 1. Die Grundidee der Kamm-Sorte besteht darin, dass die Lücke viel mehr als ein sein kann. (Sorte von Shell basiert auch auf dieser Idee, aber es ist eine Modifizierung der Einfügungssorte aber nicht Luftblase-Sorte.)

Die Lücke bricht als die Länge der Liste auf, die geteilt durch den zusammenschrumpfen lassen Faktor wird sortiert (allgemein 1.3; sieh unten), und die Liste wird mit diesem Wert (nach unten abgerundet zu einer ganzen Zahl wenn erforderlich) für die Lücke sortiert. Dann wird die Lücke durch den zusammenschrumpfen lassen Faktor wieder geteilt, die Liste wird mit dieser neuen Lücke und den Prozess-Wiederholungen sortiert, bis die Lücke 1 ist. An diesem Punkt setzt Kamm-Sorte fort, eine Lücke 1 zu verwenden, bis die Liste völlig sortiert wird. Die Endbühne der Sorte ist so zu einer Luftblase-Sorte gleichwertig, aber zu diesem Zeitpunkt sind die meisten Schildkröten befasst worden, so wird eine Luftblase-Sorte effizient sein.

Lassen Sie Faktor zusammenschrumpfen

Der zusammenschrumpfen lassen Faktor hat eine große Wirkung auf die Leistungsfähigkeit der Kamm-Sorte. Im ursprünglichen Artikel haben die Autoren 1.3 nach dem Versuchen einiger zufälliger Listen und der Entdeckung davon vorgeschlagen, allgemein am wirksamsten zu sein. Ein zu kleiner Wert verlangsamt den Algorithmus, weil mehr Vergleiche gemacht werden müssen, wohingegen ein zu großer Wert bedeutet, dass keine Vergleiche gemacht werden.

Text beschreibt eine Verbesserung, um Sorte mit dem Grundwert als der zusammenschrumpfen lassen Faktor zu kämmen (wo das goldene Verhältnis ist). Es enthält auch eine Pseudocodedurchführung mit einem vorherbestimmten Lücke-Tisch.

Schwankungen

Combsort11

Mit einem zusammenschrumpfen lassen Faktor ungefähr 1.3 gibt es nur drei mögliche Wege für die Liste von Lücken, um zu enden: (9, 6, 4, 3, 2, 1), (10, 7, 5, 3, 2, 1), oder (11, 8, 6, 4, 3, 2, 1). Experiment zeigt, dass bedeutende Geschwindigkeitsverbesserungen gebildet werden können, wenn die Lücke auf 11 gesetzt wird, wann auch immer es 9 oder 10 sonst werden würde. Diese Schwankung wird Combsort11 genannt.

Wenn entweder der Folgen, die mit 9 oder 10 beginnen, verwendet wurden, wird der Endpass mit einer Lücke 1 mit geringerer Wahrscheinlichkeit die Daten völlig sortieren, einen anderen Pass mit einer Lücke 1 nötig machend. Die Daten werden sortiert, als kein Tausch während eines Passes mit der Lücke = 1 getan wurde.

Es ist auch möglich, einen vorherbestimmten Tisch zu verwenden, der Lücken zu wählen, jeden Pass zu verwenden.

Combsort mit dem verschiedenen Ende

Wie viele ist andere Sorte effiziente Algorithmen (wie schnelle Sorte oder Verflechtungssorte), combsort in seinen früheren Pässen wirksamer, als es während der Endpässe ist, wenn es einer Luftblase-Sorte ähnelt. Combsort kann wirksamer gemacht werden, wenn die Sortieren-Methode geändert wird, sobald die Lücken Zahlen klein genug erreichen. Zum Beispiel, sobald die Lücke eine Größe von ungefähr 10 oder kleiner erreicht, den combsort aufhörend und eine einfache Zwerg-Sorte oder Cocktail-Sorte, oder, noch besser, eine Einfügungssorte tuend, wird die gesamte Leistungsfähigkeit der Sorte vergrößern.

Ein anderer Vorteil dieser Methode besteht darin, dass es kein Bedürfnis gibt, den Tausch während der Sorte-Pässe nachzugehen, um zu wissen, ob die Sorte anhalten sollte oder nicht.

Beispiele

Pseudocode

fungieren Sie combsort (Reihe-Eingang)

Lücke: = input.size

Schleife bis zur Lücke = 1 oder getauscht = falscher

Lücke: = interne Nummer (Lücke / 1.247330950103979)

wenn Lücke

Lücke: = 1

enden Sie wenn

i: = 0

getauscht: = falscher

Schleife bis ich + Lücke> = input.size

wenn eingegeben, gebe [ich]> [i+gap] ein

Tausch (Eingang [ich], Eingang [i+gap])

getauscht: = wahrer

enden Sie wenn

i: = ich + 1

Endschleife

Endschleife

beenden Sie Funktion

C

Leere comb_sort (interne Nummer *input, size_t Größe) {\

Size_t-Lücke = Größe;

bool hat = falsch getauscht;

während ((Lücke> 1) || getauscht) {\

wenn (Lücke> 1) {\

Lücke = (size_t) ((doppelte) Lücke / 1.247330950103979);

}\

getauscht = falsch;

für (size_t i = 0; Lücke + ich

int Tausch = Eingang [ich];

Eingang [ich] = Eingang [ich + Lücke];

Eingang [ich + Lücke] = Tausch;

getauscht = wahr;

}\

}\

}\

}\

</Quelle>

Siehe auch

• Luftblase-Sorte, ein allgemein langsamerer Algorithmus, ist die Basis der Kamm-Sorte.
• Cocktail-Sorte oder bidirektionale Luftblase-Sorte, ist eine Schwankung der Luftblase-Sorte, die auch das Problem von Schildkröten, obgleich weniger effektiv richtet.

Außenverbindungen

• .NET-Durchführung der Kamm-Sorte und mehrerer anderer Algorithmen