Cocktail Shaker Sorte - Cocktail shaker sort

Cocktail Shaker Art

Klasse	Sortieralgorithmus
Datenstruktur	Array
Worst-Case- Leistung	${\ displaystyle O (n ^ {2}) \,}$
Best-Case- Leistung	${\ displaystyle O (n) \,}$
Durchschnittliche Leistung	${\ displaystyle O (n ^ {2}) \,}$
Worst-Case -Raumkomplexität	${\ displaystyle O (1)}$

Die Cocktail-Shaker-Sortierung , auch bekannt als bidirektionale Blasensortierung , Cocktail-Sortierung , Shaker-Sortierung (die sich auch auf eine Variante der Auswahlsortierung beziehen kann ), Ripple-Sortierung , Shuffle-Sortierung oder Shuttle-Sortierung , ist eine Erweiterung der Blasensortierung . Der Algorithmus erweitert die Blasensortierung durch Arbeiten in zwei Richtungen. Während die Blasensortierung verbessert wird , indem Elemente schneller an den Anfang der Liste verschoben werden, werden nur geringfügige Leistungsverbesserungen erzielt.

Wie die meisten Varianten der Blasensorte wird die Cocktail-Shaker-Sortierung hauptsächlich als Lehrmittel verwendet. Leistungsstärkere Algorithmen wie Timsort oder Merge Sort werden von den Sortierbibliotheken verwendet, die in gängigen Programmiersprachen wie Python und Java integriert sind.

Pseudocode

Das einfachste Formular durchläuft jedes Mal die gesamte Liste:

procedure cocktailShakerSort(A : list of sortable items) is
    do
        swapped := false
        for each i in 0 to length(A) − 2 do:
            if A[i] > A[i + 1] then // test whether the two elements are in the wrong order
                swap(A[i], A[i + 1]) // let the two elements change places
                swapped := true
            end if
        end for
        if not swapped then
            // we can exit the outer loop here if no swaps occurred.
            break do-while loop
        end if
        swapped := false
        for each i in length(A) − 2 to 0 do:
            if A[i] > A[i + 1] then
                swap(A[i], A[i + 1])
                swapped := true
            end if
        end for
    while swapped // if no elements have been swapped, then the list is sorted
end procedure

Der erste Durchgang nach rechts verschiebt das größte Element am Ende an die richtige Stelle, und der folgende Durchgang nach links verschiebt das kleinste Element am Anfang an die richtige Stelle. Der zweite vollständige Durchgang verschiebt die zweitgrößten und zweitkleinsten Elemente an ihre richtigen Stellen und so weiter. Nachdem ich bestanden habe , befinden sich das erste i und das letzte i Element in der Liste an ihren korrekten Positionen und müssen nicht überprüft werden. Durch Kürzen des Teils der Liste, der jedes Mal sortiert wird, kann die Anzahl der Vorgänge halbiert werden (siehe Blasensortierung ).

Dies ist ein Beispiel für den Algorithmus in MATLAB / OCTAVE mit der Optimierung, sich den letzten Swap-Index zu merken und die Grenzen zu aktualisieren.

function A = cocktailShakerSort(A)
% `beginIdx` and `endIdx` marks the first and last index to check
beginIdx = 1;
endIdx = length(A) - 1;
while beginIdx <= endIdx
    newBeginIdx = endIdx;
    newEndIdx = beginIdx;
    for ii = beginIdx:endIdx
        if A(ii) > A(ii + 1)
            [A(ii+1), A(ii)] = deal(A(ii), A(ii+1));
            newEndIdx = ii;
        end
    end

    % decreases `endIdx` because the elements after `newEndIdx` are in correct order
    endIdx = newEndIdx - 1;

    for ii = endIdx:-1:beginIdx
        if A(ii) > A(ii + 1)
            [A(ii+1), A(ii)] = deal(A(ii), A(ii+1));
            newBeginIdx = ii;
        end
    end
    % increases `beginIdx` because the elements before `newBeginIdx` are in correct order
    beginIdx = newBeginIdx + 1;
end
end

Unterschiede zur Blasensortierung

Cocktail Shaker Sort ist eine leichte Variation der Bubble Sort . Es unterscheidet sich darin, dass die Liste nicht wiederholt von unten nach oben, sondern abwechselnd von unten nach oben und dann von oben nach unten durchlaufen wird. Es kann eine etwas bessere Leistung erzielen als eine Standard-Blasensorte. Der Grund dafür ist, dass die Blasensortierung die Liste nur in eine Richtung durchläuft und daher Elemente bei jeder Iteration nur einen Schritt rückwärts verschieben kann.

Ein Beispiel für eine Liste, die diesen Punkt beweist, ist die Liste (2,3,4,5,1), die nur einen Durchgang der Cocktailsorte durchlaufen müsste, um sortiert zu werden, aber bei Verwendung einer aufsteigenden Blasensorte vier geht vorbei. Ein Cocktail-Sortierpass sollte jedoch als zwei Blasensortierpass gezählt werden. Typischerweise ist die Cocktailsortierung weniger als zweimal schneller als die Blasensortierung.

Eine weitere Optimierung kann darin bestehen, dass sich der Algorithmus merkt, wo der letzte tatsächliche Austausch durchgeführt wurde. In der nächsten Iteration gibt es keine Swaps über diese Grenze hinaus und der Algorithmus hat kürzere Durchgänge. Da die Cocktail-Shaker-Sortierung bidirektional verläuft, verringert sich der Bereich möglicher Swaps, dh der zu testende Bereich, pro Durchgang, wodurch sich die Gesamtlaufzeit geringfügig verringert.

Komplexität

Die Komplexität der Cocktail-Shaker-Sortierung in Big-O-Notation gilt sowohl für den ungünstigsten als auch für den durchschnittlichen Fall, kommt jedoch der Frage näher, ob die Liste vor der Anwendung des Sortieralgorithmus größtenteils geordnet ist. Befindet sich beispielsweise jedes Element an einer Position, die sich um höchstens k (k ≥ 1) von der Position unterscheidet, an der es enden wird, wird die Komplexität der Cocktail-Shaker-Sortierung ${\ displaystyle O (n ^ {2})}$${\ displaystyle O (n)}$${\ displaystyle O (kn).}$

Die Cocktail-Shaker-Sorte wird auch in dem Buch The Art of Computer Programming kurz besprochen , zusammen mit ähnlichen Verfeinerungen der Bubble-Sorte. Abschließend erklärt Knuth über die Blasensortierung und ihre Verbesserungen:

Aber keine dieser Verfeinerungen führt zu einem Algorithmus, der besser ist als die gerade Einfügung [dh die Einfügungssortierung ]; und wir wissen bereits, dass das gerade Einsetzen nicht für großes N geeignet ist  . [...] Kurz gesagt, die Blasensorte scheint nichts zu empfehlen zu haben, außer einem eingängigen Namen und der Tatsache, dass dies zu einigen interessanten theoretischen Problemen führt.

-  DE Knuth

Verweise

Quellen

• Hartenstein, R. (Juli 2010). "Ein neues Weltmodell des Rechnens" (PDF) . Die große Herausforderung, Computing neu zu erfinden . Belo Horizonte , Brasilien: CSBC. Archiviert vom Original (PDF) am 07.08.2013 . Abgerufen am 14.01.2011 .

Externe Links

• Interaktive Demo der Cocktail-Art
• Java-Quellcode und eine animierte Demo der Cocktail-Sortierung (als bidirektionale Blasensortierung bezeichnet) sowie verschiedene andere Algorithmen
• ".NET Implementierung der Cocktail-Sortierung und mehrerer anderer Algorithmen" . Archiviert vom Original am 12.02.2012.