Kammsortierung - Comb sort

Kammsortierung

Kammsortierung mit Schrumpfungsfaktor k = 1,24733
Klasse	Sortieralgorithmus
Datenstruktur	Array
Worst-Case- Leistung	${\ displaystyle O (n ^ {2})}$
Best-Case- Leistung	${\ displaystyle \ Theta (n \ log n)}$
Durchschnittliche Leistung	${\ displaystyle \ Omega (n ^ {2} / 2 ^ {p})}$ , wobei p die Anzahl der Inkremente ist
Worst-Case -Raumkomplexität	${\ displaystyle O (1)}$

Die Kammsortierung ist ein relativ einfacher Sortieralgorithmus, der ursprünglich 1980 von Włodzimierz Dobosiewicz und Artur Borowy entwickelt und 1991 von Stephen Lacey und Richard Box wiederentdeckt (und mit dem Namen "Combsort" versehen) wurde. Die Kammsortierung verbessert die Blasensortierung auf dieselbe Weise wie die Shellsort verbessert die Sortierung beim Einfügen .

nist.gov ' s ‚abnehmenden Inkrement sort‘ Definition erwähnt der Begriff ‚Combsort‘ als Visualisierung iterative Durchläufe der Daten ‚in dem die Zähne eines Kamms Berührung;‘ Der frühere Begriff ist mit Don Knuth verbunden .

Algorithmus

Die Grundidee besteht darin, Schildkröten oder kleine Werte am Ende der Liste zu eliminieren , da diese bei einer Blasensortierung die Sortierung enorm verlangsamen. Kaninchen , große Werte am Anfang der Liste, stellen bei der Blasensortierung kein Problem dar.

Wenn bei der Blasensortierung zwei beliebige Elemente verglichen werden, haben sie immer eine Lücke (Abstand voneinander) von 1. Die Grundidee der Kammsortierung ist, dass die Lücke viel mehr als 1 sein kann. Die innere Schleife der Blasensortierung, die Wenn der eigentliche Austausch erfolgt , wird der Abstand zwischen den ausgetauschten Elementen (für jede Iteration der äußeren Schleife) in Schritten eines "Schrumpfungsfaktors" k : [ n / k , n / k ² , n / k ³ ,. .., 1].

Die Lücke beginnt mit der Länge der zu sortierenden Liste n geteilt durch den Schrumpfungsfaktor k (im Allgemeinen 1,3; siehe unten), und ein Durchgang der oben genannten modifizierten Blasensortierung wird mit dieser Lücke angewendet. Dann wird die Lücke erneut durch den Schrumpfungsfaktor geteilt, die Liste wird mit dieser neuen Lücke sortiert und der Vorgang wird wiederholt, bis die Lücke 1 ist. Zu diesem Zeitpunkt wird die Kammsortierung mit einer Lücke von 1 fortgesetzt, bis die Liste vollständig sortiert ist. Die letzte Stufe der Sortierung entspricht somit einer Blasensortierung, aber zu diesem Zeitpunkt sind die meisten Schildkröten bereits behandelt, sodass eine Blasensortierung effizient ist.

Der Schrumpfungsfaktor hat einen großen Einfluss auf die Effizienz der Kammsortierung. k = 1,3 wurde von den Autoren des Originalartikels nach empirischen Tests an über 200.000 Zufallslisten als idealer Schrumpfungsfaktor vorgeschlagen. Ein zu kleiner Wert verlangsamt den Algorithmus durch unnötig viele Vergleiche, während ein zu großer Wert Schildkröten nicht effektiv behandelt, sodass viele Durchgänge mit einer Lückengröße erforderlich sind.

Das Muster wiederholter Sortierdurchläufe mit abnehmenden Lücken ähnelt Shellsort, aber in Shellsort wird das Array bei jedem Durchgang vollständig sortiert, bevor zur nächstkleineren Lücke übergegangen wird. Die Durchgänge der Kammsortierung sortieren die Elemente nicht vollständig. Dies ist der Grund, warum Shellsort-Lückensequenzen einen größeren optimalen Schrumpfungsfaktor von etwa 2,2 aufweisen.

Pseudocode

function combsort(array input) is

    gap := input.size // Initialize gap size
    shrink := 1.3 // Set the gap shrink factor
    sorted := false

    loop while sorted = false
        // Update the gap value for a next comb
        gap := floor(gap / shrink)
        if gap ≤ 1 then
            gap := 1
            sorted := true // If there are no swaps this pass, we are done
        end if

        // A single "comb" over the input list
        i := 0
        loop while i + gap < input.size // See Shell sort for a similar idea
            if input[i] > input[i+gap] then
                swap(input[i], input[i+gap])
                sorted := false
                // If this assignment never happens within the loop,
                // then there have been no swaps and the list is sorted.
             end if
    
             i := i + 1
         end loop
     end loop
end function

Python-Code

Außerdem zwei schnelle Python-Implementierungen: Eine bearbeitet die Liste (oder das Array oder einen anderen veränderlichen Typ, bei dem die für die Sprache verwendeten Operationen für die Sprache sinnvoll sind), die andere erstellt eine Liste mit denselben Werten wie die angegebenen Daten und gibt das nach dem Sortieren zurück (ähnlich der eingebauten Funktion "sortiert").

def combsort_inplace(data):
    length = len(data)
    shrink = 1.3
    _gap = length
    sorted = False
    while not sorted:
        # Python has no builtin 'floor' function, so we/I just have one variable (_gap) to be shrunk,
        # and an integer variable (gap) to store the truncation (of the other variable) in and
        # to use for stuff pertaining to indexing
        _gap /= shrink
        # gap = np.floor(_gap)
        gap = int(_gap)
        if gap <= 1:
            sorted = True
            gap = 1
        # equivalent to `i = 0; while (i + gap) < length: ...{loop body}... i += 1`
        for i in range(length - gap):
            sm = gap + i
            if data[i] > data[sm]:
                # because Python is very nice, this accomplishes the swap
                data[i], data[sm] = data[sm], data[i]
                sorted = False


def combsort(data):
    length = len(data)
    shrink = 1.3
    _gap = length
    out = list(data)
    is_sorted = False
    while not is_sorted:
        _gap /= shrink
        gap = int(_gap)
        if gap <= 1:
            is_sorted = True
            gap = 1
        for i in range(length - gap):
            sm = gap + i
            if out[i] > out[sm]:
                out[i], out[sm] = out[sm], out[i]
                is_sorted = False
    return out

Siehe auch

• Die Blasensortierung , ein im Allgemeinen langsamerer Algorithmus, ist die Grundlage für die Kammsortierung.
• Die Cocktailsorte oder bidirektionale Blasensorte ist eine Variation der Blasensorte, die auch das Problem der Schildkröten angeht, wenn auch weniger effektiv.

Verweise