Per quanto riguarda l’unione sul posto in un array

Mi sono imbattuto nella seguente domanda.

Dato un array di n elementi e un intero k dove k < n . Gli elementi { a 0a k } e { a k +1a n } sono già ordinati. Dare un algoritmo per ordinare in tempo O ( n ) e O (1) spazio.

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

Questo sembra indicare che è ansible fare nello spazio O (lg ^ 2 n). Non riesco a vedere come provare che è imansible fondersi in uno spazio costante, ma non riesco a vedere come farlo neanche io.

Modifica: Chasing references, Knuth Vol 3 – L’esercitazione 5.5.3 dice “Un algoritmo notevolmente più complicato di L. Trabb-Pardo fornisce la migliore risposta ansible a questo problema: è ansible fare una fusione stabile in tempo O (n) e stabile ordinamento in tempo O (n lg n), utilizzando solo O (lg n) bit di memoria ausiliaria per un numero fisso di variabili indice.

Altri riferimenti che non ho letto. Grazie per un problema 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 è stato chiesto più e più volte Stack Overflow domanda un numero di volte. Non ho il coraggio di contrassegnarlo come un duplicato.

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

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 un’implementazione 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.

No, non è ansible, anche se il mio lavoro sarebbe molto più facile 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 i progressi di unire l’ordinamento delle quote e degli eventi 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 delicate condizioni al contorno, leggermente più difficili della ricerca binaria per ottenere il giusto, e anche in questa (ansible) forma, e quindi un cattivo problema dei compiti a casa; ma un vero esercizio mentale.

Aggiornamento Apparentemente mi sbaglio e c’è un algoritmo che fornisce il tempo O (n) e lo spazio O (1). Ho scaricato i documenti per illuminarmi e ritirare questa risposta come errata.