Riguardo all'unione sul posto in un array

Question

mi sono imbattuto nella seguente domanda.

dato un array di n elementi e un intero k dove k < n. Elementi {un ... un _k} e { un _{k +1} ... un_n} sono già ordinati. Fornire un algoritmo per ordinare O (n) ora e O (1) spazio.

Non mi sembra che possa essere eseguito in O (n) ora e O (1) spazio. Il problema sembra davvero essere come chiedere di fare il passo di fusione di mergesort ma sul posto. Se fosse possibile, il mergesort non sarebbe stato implementato in quel modo? Non sono in grado di convincere me stesso e ho bisogno di un parere.

Answer 1

This sembra indicare che è possibile eseguire nello spazio O (lg^2 n). Non riesco a vedere come provare che è impossibile fondersi in uno spazio costante, ma non riesco a vedere come farlo neanche io.

Modifica: Riferimenti Chasing, Knuth Vol 3 - L'esercizio 5.5.3 dice "Un algoritmo notevolmente più complicato di L. Trabb-Pardo fornisce la migliore risposta possibile a questo problema: È possibile fare una fusione stabile in O (n) tempo e ordinamento stabile nel tempo O (n lg n), utilizzando solo O (lg n) bit di memoria ausiliaria per un numero fisso di variabili indice

Altro references che non ho letto. Grazie per un'interessante

Ulteriore modifica: Questo articolo afferma che l'articolo di Huang e Langston ha un algoritmo che unisce due elenchi di dimensioni m e n nel tempo O (m + n), quindi la risposta alla tua domanda sembrerebbe essere sì. Purtroppo non ho accesso all'articolo, quindi devo fidarmi delle informazioni di seconda mano. Non sono sicuro di come conciliare questo con la dichiarazione di Knuth secondo cui l'algoritmo Trabb-Pardo è ottimale. Se la mia vita dipendesse da questo, andrei con Knuth.

Ora vedo che questo era stato chiesto come prima Stack overflow question a number di volte. Non ho il coraggio di contrassegnarlo come un duplicato.

Huang B.-C. e Langston M. A., fusione sul posto pratica, comm. ACM 31 (1988) 348-352

Answer 2

No, non è possibile, anche se il mio lavoro sarebbe molto più semplice se fosse :).

Hai un fattore O (log n) che non puoi evitare. Puoi scegliere di prenderlo come tempo o spazio, ma l'unico modo per evitarlo è non ordinare. Con lo spazio O (log n) puoi creare un elenco di continuazioni che tiene traccia di dove hai nascosto gli elementi che non si adattano perfettamente. Con la ricorsione, questo può essere fatto per adattarsi all'heap di O (1), ma solo usando i frame di stack O (log n).

Ecco l'avanzamento di unire le quote e le differenze da 1 a 9.Si noti come si richiede la contabilità dello spazio di log per tracciare le inversioni dell'ordine causate dai vincoli gemelli dello spazio costante e degli scambi lineari.

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

123456789 

Ci sono alcune condizioni al contorno delicato, leggermente più difficile della ricerca binaria per ottenere il diritto, e anche di questo modulo (possibile), e quindi un problema compiti cattiva; ma un vero esercizio mentale.

Aggiornamento A quanto pare mi sbaglio e non v'è un algoritmo che fornisce O (n) e O (1) spazio. Ho scaricato i documenti per illuminarmi e ritirare questa risposta come errata.

Answer 3

Ci sono diversi algoritmi per farlo, nessuno dei quali è molto facile da intuire. L'idea chiave è di utilizzare una parte degli array per unire come buffer, quindi eseguire una fusione standard utilizzando questo buffer per lo spazio ausiliario. Se riesci a riposizionare gli elementi in modo che gli elementi del buffer siano nel posto giusto, sei d'oro.

Ho scritto an implementation di uno di questi algoritmi sul mio sito personale se sei interessato a guardarlo. Si basa sul documento "Practical In-Place Merging" di Huang and Langston. Probabilmente vorrai dare un'occhiata a quel documento per un po 'di intuizione.

Ho anche sentito che ci sono buoni algoritmi adattivi per questo, che usano un buffer a dimensione fissa di tua scelta (che potrebbe essere O (1) se vuoi), ma poi scalano elegantemente con la dimensione del buffer. Non conosco nessuno di questi argomenti, ma sono sicuro che una rapida ricerca di "Adattamento adattivo" potrebbe trasformare qualcosa.