Sortowanie przy użyciu stosów tylko do odczytu

14

Rozważ następujące ustawienie:

  • daje nam stos , który zawiera n elementów.sn
  • 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(n2))

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

Siddharth
źródło
2
Brzmi jak rejestry zachowują się jak stosy? Wygląda na to, że mówisz o operacjach push i pop. Czy to twoje pytania? Jak posortowałbyś stos za pomocą kilku stosów i operacji stosu?
AturSams
2
Za pomocą rejestrów możesz: po prostu umieścić każdą liczbę w jednym rejestrze ( O ( n ) ), a następnie zastosować zwykły algorytm sortowania ( O ( n lg n ) ). nO(n)O(nlgn)
Kaveh
1
Czy chcesz używać rejestrów ? W przeciwnym razie problem trywializuje się, jak komentuje Kaveh. O(1)
Yuval Filmus
1
Zapraszamy. Myślałem, że dostaniemy kilka stosów, a nie tylko jeden, naprawię to.
Kaveh
2
@akappa, czy jesteś pewien, że można to wykorzystać w tym widzeniu? Nie możemy utrzymać żadnej przypadkowej utraty rozmiaru większej niż 1. Nie musisz przechowywać posortowanych bloków?
Kaveh

Odpowiedzi:

1

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 2O(logn)S.T.=Ω(n2)) dolnej granicy czasu.n2)/logn

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 , k .X1,,Xk

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 kn . 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 , , dnn(ja,re1,,rek)1i0d1,,dkn jeśli znajdujemy się w linii iwynosi d i . Teraz musimy zdefiniować ukierunkowane krawędzie programu rozgałęziającego(i,d1,,dk)iw maszynie rejestrującej i długość ciągu zapisanego w Xidi

Jeśli linia ma postaći

jeśli to goto i 1Xu<Xvi1 else gotoi2

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 1d1,,dk(i,d1,,dk)dudv(i1,d1,,dk) .(i2,d1,,dk)

Jeśli linia ma postaći

, linia gotoX1tail(X2)i

następnie jest strzałka z dowolnego węzła do ( i , d 2 - 1 , , d(i,d1,,dk) .(i,d21,,dk)

Jeśli linia ma postaći

, goto lineprint(head(Xu))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,d1,,dk)(i,d1,,dk)du

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 )nkO(logn)

Siddharth
źródło
0

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

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


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

lognccnlogn+cn2logn2+cn4logn4+ ...=O(nlogn)O(nlogn)

cero
źródło
Nie jestem pewien, czy rozumiem. Jak możemy na przykład skopiować górną połowę stosu w odwrotnej kolejności na inny stos, skoro nigdy nie możemy wepchnąć żadnego elementu na żaden stos?
Siddharth
Nie możemy pchać żadnego nowego elementu na stos, ale zgodnie z 5 jesteśmy w stanie przepchnąć górny element jednego stosu na drugi. Tak więc kopiowanie stosu w odwrotnej kolejności wymaga co najwyżej liniowego czasu. Więc przypuszczam, że nie o to prosiliście?
cero
Nie możesz naciskać niczego na inne przedmioty, jak wyjaśniono w pytaniu.
Kaveh