Sortowanie przy użyciu stosów tylko do odczytu

Rozważ następujące ustawienie:

• daje nam stos , który zawiera n elementów.$s$$n$
• możemy użyć stałej liczby dodatkowych stosów .$O(1)$
• na tych stosach możemy zastosować następujące operacje:
  1. sprawdź, czy stos jest pusty,
  2. porównaj najlepsze przedmioty z dwóch stosów,
  3. usuń najwyższy element ze stosu,
  4. wydrukuj najwyższy element na stosie,
  5. skopiuj górny element stosu do innego stosu,
  6. skopiuj zawartość jednego stosu na inny stos.

Pamiętaj, że są to jedyne dozwolone operacje. Nie możemy zamieniać przedmiotów i nie wolno nam wpychać żadnego elementu na żaden stos, z wyjątkiem kopiowania górnego elementu do stosu (po czym poprzednia zawartość stosu docelowego jest odrzucana i będzie zawierać tylko skopiowany element) .

Oto algorytm do sortowania stosów za pomocą porównań :$O(n^2)$

last := empty
for i from 1 to n
  min := empty
  w := s
  while w is not empty
    if w.top > last and w.top < min
      min := w.top
    delete w.top
  print min
  last := min

Czy możemy zrobić lepiej?

Czy istnieje program, który drukuje posortowaną listę elementów w stosach, używając tylko porównań ?$O(n\log n)$

Myślę, że mogę teraz zademonstrować nietrywialną dolną granicę. Chodzi o to, aby wdrożyć dowolny taki program z rodziną porównawczych programów rozgałęziających. Założenie „tylko do odczytu” oznacza, że ​​nasza rodzina programów rozgałęziających zużywa niewiele, tj. , przestrzeni. Następnie stosujemy dolną granicę S T = Ω ( n 2 ) udowodnioną przez Borodina i in. w „Kompromisie czasoprzestrzennym dla sortowania na nieświadomych maszynach”. To daje nam n $O(\log n)$$ST=\Omega(n^2)$ dolnej granicy czasu.$n^2/\log n$

Mówiąc bardziej szczegółowo: możemy zrezygnować z operacji 5 powyżej. Mówiąc luźniej, jeśli możemy już porównać nagłówki dwóch list i wydrukować nagłówek listy, nie musimy izolować nagłówka listy w konkretnym rejestrze. Zakładając to, widzimy, że każdy rejestr w maszynie zawsze przechowuje tylko końcowy podciąg danych wejściowych.

Załóżmy, że nasz program rejestrów ma wierszy kodu i rejestrów k , X 1 , $\ell$$k$ .$X_1,\dots,X_k$

Fix . Tworzymy porównawczy program rozgałęziający dla ciągów o długości n w następujący sposób. Utwórz węzeł dla każdej krotki ( i , d 1 , … , d k ), gdzie 1 ≤ i ≤ ℓ i 0 ≤ d 1 , … , d k ≤ n . Chodzi o to, że obliczenia w maszynie rejestrującej odpowiadają ścieżkom w programie rozgałęziającym, a my jesteśmy w węźle ( i , d 1 , … , $n$$n$$(i,d_1,\dots,d_k)$$1\le i\le \ell$$0\le d_1 ,\dots, d_k \le n$ jeśli znajdujemy się w linii iwynosi d i . Teraz musimy zdefiniować ukierunkowane krawędzie programu rozgałęziającego$(i,d_1 ,\dots, d_k)$$i$w maszynie rejestrującej i długość ciągu zapisanego w $X_i$$d_i$

Jeśli linia ma postać$i$

jeśli to goto i $X_u<X_v$$i_1$ else goto$i_2$

następnie dla wszystkich , węzeł ( i , d 1 , … , d k ) jest oznaczony poprzez porównanie d u-tego i d v-tego elementu wejściowego, a „prawdziwa” krawędź przechodzi do ( i 1 , d 1 , … , d k ) , a „fałszywa” krawędź do ( i 2 , d $d_1,\dots,d_k$$(i,d_1,\dots,d_k)$$d_u$$d_v$$(i_1,d_1,\dots,d_k)$ .$(i_2,d_1,\dots,d_k)$

Jeśli linia ma postać$i$

, linia goto$X_1 \leftarrow tail(X_2)$$i'$

następnie jest strzałka z dowolnego węzła do ( i ′ , d 2 - 1 , … , $(i,d_1,\dots,d_k)$ .$(i',d_2-1,\dots,d_k)$

Jeśli linia ma postać$i$

, goto line$print(head(X_u))$$i'$

Następnie znajduje się strzałka z dowolnego węzła do ( I ' , d 1 , ... , d k ) , który jest oznaczony przez D u -ty węzła wejścia.$(i,d_1,\dots,d_k)$$(i',d_1,\dots,d_k)$$d_u$

Mam nadzieję, że te przykłady wyjaśniają, w jaki sposób zamierzam zbudować program rozgałęziający. Kiedy wszystko jest powiedziane i zrobione, ten program rozgałęzienia ma co najwyżej węzłów, a więc ma miejsce O ( log n $\ell\cdot n^k$$O(\log n)$

Czy potrafisz liczyć elementy? Myślę, że wtedy jest dość łatwa implementacja Mergesort. Gdybyś był w stanie umieścić dodatkowe symbole na stosie, możesz rozwiązać go za pomocą 3 takich stosów:

Jeśli mamy tylko jeden element, lista jest już posortowana. Załóżmy teraz, że posortowaliśmy już górną połowę stosu. Możemy skopiować górną połowę (w odwrotnej kolejności) do drugiego stosu i umieścić na nim symbol separacji. Teraz znów mamy 3 stosy (ponieważ możemy zignorować już posortowane symbole poniżej symbolu separacji) i możemy posortować dolną połowę. Wreszcie możemy skopiować posortowaną dolną połowę do trzeciego stosu w odwrotnej kolejności i scalić obie połówki z powrotem do oryginalnego stosu.

Wszystkie operacje kosztują czas liniowy, dlatego posortowaliśmy listę w $O(n \log n)$

(Uwaga: potrzebujemy stosów o rozmiarze ze względu na symbole separacji, ale można to łatwo poprawić za pomocą innego stosu)$n \log n$

Ponieważ nie możesz umieścić nowych elementów na stosie, możesz mieć problemy w punktach separacji. Aby rozwiązać ten problem, możesz wykonać następujące czynności z kilkoma dodatkowymi stosami:

Skopiuj górne elementy do dodatkowego stosu, a następnie postępuj z pozostałymi elementami jak poprzednio. Teraz znasz dokładnie liczbę elementów, które musisz wziąć pod uwagę na każdym etapie, a zatem nie potrzebujesz żadnych symboli separacji.$n-2^{\lfloor \log n\rfloor}$

$\log n$$c$$cn \log n+c\frac{n}{2} \log \frac{n}{2}+c\frac{n}{4} \log \frac{n}{4}+\ ... = O(n \log n)$$O(n \log n)$