En ce qui concerne la fusion sur place dans un tableau

Question

Je suis tombé sur la question suivante.

Etant donné un ensemble de n éléments et un nombre entier k où k < n. Les éléments {un ... un _k} et { un _{k ... unn} sont déjà triés. Donner un algorithme pour trier en O (n) l'heure et l'espace O (1).}

Il ne me semble pas que cela puisse être fait en O (n) temps et O (1) espace. Le problème semble vraiment être de savoir comment faire l'étape de fusion de mergesort mais in-place. Si c'était possible, la fusion ne serait-elle pas mise en œuvre de cette façon? Je suis incapable de me convaincre et j'ai besoin d'une opinion.

Answer 1

This semble indiquer qu'il est possible de faire dans l'espace O (lg^2 n). Je ne vois pas comment prouver qu'il est impossible de fusionner dans un espace constant, mais je ne vois pas non plus comment le faire. Knuth Vol 3 - Exercice 5.5.3 dit: "Un algorithme considérablement plus compliqué de L. Trabb-Pardo fournit la meilleure réponse possible à ce problème: Il est possible de faire une fusion stable en O (n) temps et tri stable en temps O (n lg n), en utilisant seulement O (lg n) bits de mémoire auxiliaire pour un nombre fixe de variables d'index

Plus Plus je n'ai pas lu Merci pour une intéressante

Autre édition: Cet article prétend que l'article de Huang et Langston a un algorithme qui fusionne deux listes de taille m et n dans le temps O (m + n), donc la réponse à votre question semblerait être oui. Malheureusement, je n'ai pas accès à l'article, je dois donc faire confiance à l'information de seconde main. Je ne sais pas comment concilier cela avec la déclaration de Knuth selon laquelle l'algorithme de Trabb-Pardo est optimal. Si ma vie en dépendait, j'irais avec Knuth.

Je vois maintenant que cela a été demandé comme et plus tôt Stack Overflow question un number fois. Je n'ai pas le cœur de le signaler comme un doublon.

Huang B.-C. et Langston M. A., fusion pratique in situ, Comm. ACM 31 (1988) 348-352

Answer 2

Non, ce n'est pas possible, bien que mon travail serait beaucoup plus facile si c'était :).

Vous avez un facteur O (log n) que vous ne pouvez pas éviter. Vous pouvez choisir de le prendre comme temps ou espace, mais la seule façon de l'éviter est de ne pas trier. Avec l'espace O (log n) vous pouvez construire une liste de continuations qui gardent la trace de l'endroit où vous avez caché les éléments qui ne vous convenaient pas. Avec la récursion, ceci peut être fait pour tenir dans le tas O (1), mais c'est seulement en utilisant des cadres de pile O (log n) à la place.

Voici la progression des cotes de fusion et de tri de 1-9.Remarquez comment vous avez besoin de la comptabilité log-espace pour suivre les inversions d'ordre causées par les contraintes jumelles de l'espace constant et des échanges linéaires.

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

123456789 

Il y a des conditions aux limites délicates, un peu plus difficile que la recherche binaire pour obtenir le droit, et même dans ce (possible) forme, et donc un problème de mauvais devoirs; mais un très bon exercice mental. Apparemment, je me trompe et il y a un algorithme qui fournit l'espace O (n) et l'espace O (1). J'ai téléchargé les papiers pour m'éclairer et retirer cette réponse comme incorrecte.

Answer 3

Il existe plusieurs algorithmes pour cela, dont aucun n'est très facile à comprendre. L'idée principale est d'utiliser une partie des tableaux pour fusionner en tant que tampon, puis d'effectuer une fusion standard à l'aide de ce tampon pour l'espace auxiliaire. Si vous pouvez ensuite repositionner les éléments afin que les éléments de la mémoire tampon soient au bon endroit, vous êtes en or.

J'ai écrit an implementation de l'un de ces algorithmes sur mon site personnel si vous souhaitez le voir. Il est basé sur l'article "Practical In-Place Merging" par Huang et Langston. Vous aurez probablement envie de regarder par-dessus ce document pour un aperçu. J'ai également entendu dire qu'il existe de bons algorithmes adaptatifs pour cela, qui utilisent un tampon de taille fixe de votre choix (qui pourrait être O (1) si vous le souhaitez), mais qui s'adaptent élégamment à la taille de la mémoire tampon. Je ne connais aucun d'entre eux de la tête, mais je suis sûr qu'une recherche rapide de "fusion adaptative" pourrait changer quelque chose.