Was ist der effizienteste Konstantraum-Sortieralgorithmus?

Ich suche nach einem Sortieralgorithmus für int-Arrays, der kein anderes Byte als die Größe des Arrays zuweist und auf zwei Befehle beschränkt ist:

1. SWAP: Tauschen Sie den nächsten Index gegen den aktuellen aus.

2. MOVE: bewegt den Cursor zum Index +1 oder -1;

Das heißt, Sie können weder nicht benachbarte Indizes tauschen, noch den Index tauschen 100, nachdem Sie gerade den Index getauscht haben 10. Was ist der effizienteste Algorithmus - dh derjenige, der die geringere Menge an Gesamtbewegungen verwendet?

Betrachten Sie Cocktail-Shaker-Sorte , die eine bidirektionale Version der Bubble-Sorte ist. Sie sprudeln von niedrig nach hoch und dann (dies ist der hinzugefügte Teil) sprudeln Sie von hoch nach niedrig. Wiederholen Sie dies, bis Sie fertig sind. Dies ist immer noch , aber es werden im Durchschnitt deutlich weniger Durchgänge ausgeführt, da kleine Elemente nahe dem oberen Ende des Arrays in einem einzigen Durchgang anstelle von N Durchgängen an ihre endgültige Position verschoben werden. Außerdem können Sie die niedrigsten und höchsten Positionen verfolgen, an denen ein Swap stattgefunden hat. nachfolgende Durchläufe müssen nicht über diese Punkte hinaus gescannt werden.$O(n^2)$

Die Anzahl der Auslagerungen benachbarter Elemente, die zum Ordnen eines Arrays erforderlich sind, entspricht der Anzahl der Inversionen im Array. Mit insgesamt n Elementen gibt es höchstens n * (n-1) / 2 Inversionen, so dass die Blasensortierung die asymptotisch optimale Anzahl von Swaps in diesem Modell ergibt.

Der einzige Algorithmus mit den beiden von Ihnen genannten Operatoren, der sehr effizient ist, ist die Blasensortierung. Die Komplexität des Algorithmus ist im schlimmsten Fall .$O(n^2)$

Ich gehe auch davon aus, dass wir neben den beiden Operationen auch überprüfen können, ob wir am rechten (Op 3) oder am linken Ende (Op 4) sind, entweder mithilfe der Sentinels und oder durch eine Operation in der Liste . Wir sollten auch eine Vergleichsoperation (op. 5) separat geben oder mit einer Swap-Operation kombinieren. Wenn die Vergleichsoperation mit der Swap-Operation kombiniert ist, muss sie uns mitteilen, ob der Swap durchgeführt wurde oder nicht.+ $-\infty$$+\infty$

Der Algorithmus, der kein Boolesches Flag verwendet, um festzustellen, ob ein Element vertauscht wurde, wird im Folgenden beschrieben (der Trick, die Informationen im Status der Maschine und nicht im Speicher zu belassen):

Start:
    Do until we are not at the leftmost position (Op 4)
        move left (Op 2b)

Check:
    If we are at rightmost position (Op 3)
        goto Finished:
    If current value is larger than next value (Op 5)
        goto Unfinished:
    move right (Op 2a)
    Repeat Check:

Unfinished:
    If we are at rightmost position (Op 3)
        goto Start:
    If current value is larger than next value (Op 5)
        swap the elements (Op 1) and move right (Op 2a)
    Repeat Unfinished:

Finished:
    The list is sorted now, output it.

Die Lösung von Eric Lippert, der Gnomensorte, funktioniert auch, weil es sich im Grunde um eine Zwei-Wege-Blasensorte handelt.