16 votes

Concernant la fusion sur place dans un tableau

J'ai rencontré la question suivante.

Étant donné un tableau de n éléments et un entier kk < n. Les éléments {a0...a<i>k</i>} et {a<i>k</i>+1...a<em>n</em>} sont déjà triés. Donnez un algorithme pour trier en temps O(n) et espace O(1).

Il ne me semble pas que cela puisse être fait en temps O(n) et espace O(1). Le problème semble vraiment demander comment faire l'étape de fusion de merge sort mais sur place. Si c'était possible, le mergesort ne serait-il pas implémenté de cette manière ? Je n'arrive cependant pas à me convaincre et j'ai besoin d'un avis.

9voto

deinst Points 8706

Cela semble indiquer qu'il est possible de le faire en espace O(lg^2 n). Je ne vois pas comment prouver qu'il est impossible de fusionner en espace constant, mais je ne vois pas non plus comment le faire.

Éditer : En suivant des références, 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 temps O(n) et un 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 de références que je n'ai pas lues. Merci pour un problème intéressant.

Édition supplémentaire : Cet article affirme que l'article de Huang et Langston propose un algorithme qui fusionne deux listes de taille m et n en temps O(m + n), donc la réponse à votre question semblerait être oui. Malheureusement, je n'ai pas accès à l'article, donc je dois me fier à l'information de seconde main. Je ne sais pas comment concilier cela avec l'affirmation de Knuth selon laquelle l'algorithme de Trabb-Pardo est optimal. Si ma vie en dépendait, je choisirais Knuth.

Je vois maintenant que cela a été demandé comme une question précédente sur Stack Overflow question à plusieurs reprises. Je n'ai pas le cœur à le signaler comme un doublon.

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

2voto

templatetypedef Points 129554

Il existe plusieurs algorithmes pour faire cela, aucun d'entre eux n'est très facile à intuiter. L'idée clé est d'utiliser une partie des tableaux à fusionner comme tampon, puis de réaliser une fusion standard en utilisant ce tampon comme espace auxiliaire. Si vous pouvez alors repositionner les éléments de manière à ce que les éléments du tampon soient à la bonne place, vous êtes gagnant.

J'ai rédigé une implémentation de l'un de ces algorithmes sur mon site personnel si vous êtes intéressé à y jeter un coup d'œil. Il est basé sur l'article "Practical In-Place Merging" de Huang and Langston. Vous voudrez probablement consulter cet article pour obtenir quelques informations.

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 vouliez), mais qui évoluent élégamment avec la taille du tampon. Je ne connais aucun de ceux-ci de tête, mais je suis sûr qu'une rapide recherche de "fusion adaptative" pourrait vous donner des résultats.

1voto

Recurse Points 2019

Non, ce n'est pas possible, même si mon travail serait beaucoup plus facile si c'était le cas :).

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 un espace O(log n), vous pouvez construire une liste de continuations qui suivent où vous avez caché les éléments qui ne s'adaptent pas tout à fait. Avec la récursivité, cela peut être fait pour tenir dans un tas O(1), mais cela n'est possible qu'en utilisant des trames de pile O(log n).

Voici l'avancée du tri fusion des nombres pairs et impairs de 1 à 9. Remarquez comment vous avez besoin d'un espace log pour suivre les inversions d'ordre causées par les contraintes jumelles d'espace constant et d'échanges linéaires.

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

123456789

Il y a quelques conditions limites délicates, légèrement plus difficiles que la recherche binaire pour les maîtriser, et même dans cette forme (possible), et donc un mauvais problème de devoir; mais un très bon exercice mental.

Mise à jour Apparemment, je me suis trompé et il existe un algorithme qui fournit un temps O(n) et un espace O(1). J'ai téléchargé les articles pour m'éclairer et retire donc cette réponse comme incorrecte.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X