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

19

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?

MaiaVictor
źródło
13
Nie jest to dziwne, jest to fizyczna maszyna, która posortuje listę wózków przyklejonych do zwiniętej taśmy. Urządzenie może jedynie przesuwać taśmę do przodu lub do tyłu i może wymieniać tylko sąsiednie karty. W prawdziwym świecie nie można się teleportować, więc są to ograniczenia ...
MaiaVictor
2
Więc kiedy mówisz, że chcesz algorytmu, który nie przydziela żadnego bajtu innego niż rozmiar tablicy , myślę, że odwołujesz się tylko do przechowywania elementów, prawda? Nadal mogę przydzielać liczniki i tym podobne?
Darkhogg
5
Oh, pewnie. Oczywiście. Możesz przydzielić dodatkowe struktury. Możesz nawet przydzielić całą tablicę i wykonać wiele naprawdę ciężkich obliczeń, co liczy się jako 0. Jedyną rzeczą, którą musisz zminimalizować, jest liczba SWAP / MOVE rzeczywistej fizycznej maszyny, ponieważ jest ona wolna. Sortowanie bąbelkowe jest najlepsze, jakie mogłem wymyślić, ale sądziłem, że powinny być lepsze opcje.
MaiaVictor
1
Nie sądzę, że istnieje taki algorytm. Bez jakiejkolwiek dodatkowej pamięci, że nie będziesz mieć możliwość przechowywania dowolnego stanu sterowania.
Raphael
1
@svrm: tak, z nieograniczoną pamięcią RAM i możliwością kopiowania taśmy do pamięci RAM i wykonywania dowolnych obliczeń za darmo, algorytm „wypróbuj wszystko i zastosuj najlepsze” jest optymalny pod względem liczby ruchów taśmy. Jest mało prawdopodobne, aby było to praktyczne, ale dzieje się tak, ponieważ w praktyce czas działania wyniósłby miliardy lat, a nie 0 ;-) Jeśli skopiowanie taśmy o długości N do pamięci RAM kosztuje N, to naiwna brutalna siła może nie być optymalna, ale mieści się w zakresie N optymalnego. Ale żadna z tych cech nie jest specyficzna dla twojego problemu: wiele problemów, o których mowa w ten sposób, można rozwiązać „offline” za pomocą fałszywego algorytmu.
Steve Jessop

Odpowiedzi:

13

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(n2)

Zwol
źródło
4

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.

Charles
źródło
W rzeczywistości sortowanie bąbelkowe zapewni dokładnie optymalną liczbę zamian. Jednak dla każdej permutacji istnieje kilka sposobów na optymalną liczbę zamian i nie jest oczywiste, który z nich zmniejsza całkowitą liczbę ruchów. (Przez sortowanie bąbelkowe mam na myśli „wybierz największy nieposortowany i przenieś go na koniec posortowanego”)
Peter Kravchuk
4

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

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.+ +

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.

Shreesh
źródło
A co z rodzajem wstawiania?
Darkhogg
Sortowanie bąbelkowe wymaga co najmniej dwóch liczników pętli, które są już więcej niż dozwolone.
Raphael
1
Nie, możesz iść w lewo i prawo, a następnie od prawej do lewej, dopóki nie będzie żadnych zmian (czyli maksymalnie n razy) bez użycia licznika. Nie potrzebujesz nawet więcej miejsca na flagę boolowską, aby zauważyć, czy nastąpiła zmiana. W przypadku zmiany wystarczy przejść do innego podprogramu, który robi to samo, z tym wyjątkiem, że jest to inny podprogram.
Shreesh
1
I oczywiście zakładam, że możesz czytać puste miejsca na obu końcach, abyś mógł wiedzieć, że jest to początek lub koniec listy. Zakładam również, że czytamy zarówno bieżący, jak i następny element, aby wiedzieć, czy musimy zamienić.
Shreesh
1
Lub, jeśli zmodyfikujemy swap operatora jako „zamień, jeśli nie w porządku rosnącym”.
Shreesh