Regarding in-place merge in an array

Natknąłem się na następujące pytanie.

Podano tablicę N elementów i liczbę całkowitą k Gdzie k N . Elementy {a0...ak} oraz {ak+1...an} są już posortowane. Podaj algorytm sortowania w o (N) czasie I O (1) przestrzeni.

Wydaje mi się, że nie można tego zrobić w O(N) czasie I O(1) przestrzeni. Na problem naprawdę wydaje się być pytaniem, Jak zrobić etap scalania mergesort, ale na miejscu. Gdyby to było możliwe, czy mergesort nie byłby realizowany w ten sposób? Nie jestem jednak w stanie się przekonać i potrzebuję opinii.

Author: templatetypedef, 2010-07-20
Source

3 answers

To wydaje się wskazywać, że można to zrobić w przestrzeni O (lg^2 n). Nie widzę, jak udowodnić, że nie da się połączyć w stałej przestrzeni, ale też nie widzę, jak to zrobić.

Edytuj: Knuth Vol 3-ćwiczenie 5.5.3 mówi: "znacznie bardziej skomplikowany algorytm L. Trabb-Pardo zapewnia najlepszą możliwą odpowiedź na ten problem: możliwe jest stabilne scalanie w czasie O(n) i stabilne sortowanie w czasie O(N lg n), używając tylko o(lg n) bitów O (N). pamięć pomocnicza dla ustalonej liczby zmiennych indeksowych.

Więcej odniesień których nie czytałem. Dzięki za ciekawy problem.

Dalsza edycja: Ten artykuł twierdzi, że artykuł Huanga i Langstona ma algorytm, który łączy dwie listy wielkości m I n w czasie O (m + n), więc odpowiedź na twoje pytanie wydaje się być twierdząca. Niestety nie mam dostępu do artykułu, więc muszę zaufać informacji z drugiej ręki. Nie wiem, jak to pogodzić. z twierdzeniem Knutha, że algorytm Trabb-Pardo jest optymalny. Gdyby zależało od tego moje życie, wybrałbym Knutha.

Teraz widzę, że to zostało zadane jako i wcześniej Stack Overflow pytanie a Liczba razy. Nie mam serca, by oznaczyć to jako DUPLIKAT.

Huang B.-C. and Langston M. A., Practical in-place merging, Comm. ACM 31 (1988) 348-352

 9
Author: deinst,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:13:31

Istnieje kilka algorytmów, z których żaden nie jest łatwy do intuicji. Kluczową ideą jest użycie części tablic do scalania jako bufora, a następnie wykonanie standardowego scalania przy użyciu tego bufora dla przestrzeni pomocniczej. Jeśli możesz zmienić położenie elementów tak, aby elementy bufora znajdowały się we właściwym miejscu, będziesz złoty.

Napisałem implementację jednego z tych algorytmów na mojej osobistej stronie, jeśli jesteś zainteresowany obejrzeniem go. Opiera się na referat" praktyczne łączenie w miejscu " autorstwa Huanga i Langstona. Prawdopodobnie będziesz chciał przejrzeć ten papier, aby uzyskać wgląd.

Słyszałem również, że istnieją do tego dobre algorytmy adaptacyjne, które wykorzystują wybrany przez Ciebie bufor o stałej wielkości( który może być O(1), jeśli chcesz), ale następnie skaluj elegancko z rozmiarem bufora. Nie znam żadnego z nich z głowy, ale jestem pewien, że szybkie wyszukiwanie "adaptive merge" może coś znaleźć.

 2
Author: templatetypedef,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-11-13 23:40:32

Nie to nie jest możliwe, chociaż moja praca byłaby o wiele łatwiejsza, gdyby była :).

Masz Współczynnik o (log n), którego nie możesz uniknąć. Możesz wziąć to jako czas lub przestrzeń, ale jedynym sposobem na uniknięcie tego jest nie sortowanie. Za pomocą o (log n) space możesz zbudować listę ciągów, które śledzą, gdzie Ukryłeś elementy, które nie do końca pasowały. W przypadku rekurencji może to być dopasowane do O(1) heap, ale jest to tylko przez użycie ramek stosu o (log n).

Oto postęp merge-sortowanie kursów i wyrównuje się od 1-9. Zauważ, jak potrzebujesz księgowania log-space, aby śledzić inwersje kolejności spowodowane podwójnymi ograniczeniami stałej przestrzeni i zamiany liniowe.

.     -
135792468
 .   -
135792468
  :  .-
125793468
   : .-
123795468
    #.:-
123495768
     :.-
123459768
      .:-
123456798
       .-
123456789

123456789

Istnieją pewne delikatne warunki brzegowe, nieco trudniejsze niż wyszukiwanie binarne, aby uzyskać prawo, a nawet w tej (możliwej) formie, a zatem zły problem z pracą domową; ale naprawdę dobre ćwiczenie umysłowe.

Update Najwyraźniej się mylę i istnieje algorytm, który zapewnia Czas O (n) I O (1) przestrzeń. Ściągnąłem dokumenty, aby się oświecić i wycofać tę odpowiedź jako błędną.

 1
Author: Recurse,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-07-21 01:29:54