Jaki jest najbardziej wydajny algorytm sortowania w stałej przestrzeni?

Szukam algorytmu sortowania dla tablic int, który nie przydziela żadnych bajtów innych niż rozmiar tablicy i jest ograniczony do dwóch instrukcji:

1. SWAP: zamień następny indeks na bieżący;

2. MOVE: przesuwa kursor do indeksu +1 lub -1;

Oznacza to, że nie można zamieniać niesąsiadujących indeksów ani zamieniać indeksu 100po zamianie indeksu 10. Jaki jest najbardziej wydajny algorytm - tj. Taki, który wykorzystuje mniejszą liczbę całkowitych ruchów?

Rozważ sortowanie koktajli , które jest dwukierunkową wersją sortowania bąbelkowego. Sortujesz bąbelkami od niskiego do wysokiego, a następnie (jest to część dodana) sortujesz bąbelkowo od wysokiego do niskiego, powtarzaj aż do zakończenia. Nadal jest to , ale powoduje średnio znacznie mniej przebiegów, ponieważ małe elementy w pobliżu górnego końca tablicy zostaną przesunięte do ich ostatecznej pozycji w jednym przejściu zamiast N przejść. Możesz także śledzić najniższe i najwyższe pozycje, w których nastąpiła zamiana; kolejne podania nie muszą skanować poza te punkty.$O(n^2)$

Liczba zamian sąsiednich elementów potrzebnych do zamówienia tablicy jest równa liczbie inwersji w tablicy. Przy sumie n elementów istnieje co najwyżej n * (n-1) / 2 inwersje, więc sortowanie bąbelkowe daje asymptotycznie optymalną liczbę zamian w tym modelu.

Jedynym algorytmem z dwoma wspomnianymi operatorami, który jest dość wydajny, jest sortowanie bąbelkowe. Złożoność algorytmu wynosi w najgorszym przypadku .$O(n^2)$

Zakładam, że oprócz dwóch operacji, możemy również sprawdzić, czy jesteśmy na skrajnej prawej (Op 3), czy skrajnie lewej (Op 4), albo za pomocą wartowników i albo przez jakąś operację na liście . Powinniśmy także mieć operację porównania (Op 5) podaną osobno lub w połączeniu z operacją zamiany. Jeśli operacja porównania jest połączona z operacją wymiany, to musi nam powiedzieć, czy zamiana została wykonana, czy nie.+ $-\infty$$+\infty$

Algorytm, który nie używa flagi boolowskiej, aby wiedzieć, czy zamieniliśmy dowolny element, jest podany poniżej (sztuczka polegająca na utrzymywaniu informacji w stanie maszyny, a nie pamięci):

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.

Rozwiązanie Erica Lipperta, gnome sort, również działa, ponieważ w zasadzie jest to dwukierunkowy sortowanie bąbelkowe.