J'ai trouvé ce post Comment faire itératif tri rapide sans utiliser stack en c? mais la réponse suggérée utilise un tableau de pile en ligne! (Seule une quantité constante d'espace supplémentaire est autorisée)
5 Réponses :
Eh bien, c'est possible, car j'ai implémenté un tri rapide dans fortran IV (c'était il y a longtemps, et avant que le langage ne prenne en charge la récursivité - et c'était pour un pari). Cependant, vous avez besoin d'un endroit (un grand tableau ferait l'affaire) pour vous souvenir de votre état lorsque vous effectuez des tâches individuelles.
C'est beaucoup plus facile de manière récursive ...
Aussi sans pile?
fortran iv n'avait ni récursivité ni pile
Pas seulement une pile implicite pour les appels de fonction… n'importe quelle pile…
lorsque vous dites que vous avez besoin d'un grand tableau, vous avez essentiellement une pile.
Et bien non. Vous avez un éventail d'états. C'est ce que le PO a demandé. il n'a pas dit `` sans utiliser de mémoire '', il a dit `` sans utiliser de pile ''
Quicksort est par définition un algorithme de recherche "diviser et conquérir", l'idée est que vous divisez le tableau donné en partitions plus petites. Vous divisez donc le problème en sous-problèmes, c'est plus facile à résoudre. Lorsque vous utilisez Quicksort sans récursivité, vous avez besoin d'une structure quelconque pour stocker les partitions que vous n'utilisez pas à ce moment-là. C'est pourquoi la réponse de la post utilise un tableau pour rendre le tri rapide non récursif.
le tableau en ligne utilisé pour la comptabilité imite en fait l'utilisation d'une pile autonome dans le même but; mais mon intention est de limiter l'espace supplémentaire à une taille constante uniquement
Le tri rapide peut-il être implémenté en C sans pile ni récursivité?
Quicksort nécessite que deux chemins soient suivis à partir de chaque partitionnement non trivial: un nouveau partitionnement de chaque (sous) partition. Les informations sur le partitionnement précédent (les limites de l'une des partitions résultantes) doivent être reportées à chaque nouveau partitionnement. La question est donc de savoir où vivent ces informations? En particulier, où se trouvent les informations sur une partition pendant que le programme travaille sur l'autre?
Pour un algorithme série, la réponse est que les informations sont stockées sur une pile ou une file d'attente ou un équivalent fonctionnel de l'un d'entre eux. Toujours, parce que ce sont nos noms pour les structures de données qui servent le but nécessaire. En particulier, la récursivité est un cas particulier, pas une alternative. Dans un tri rapide récursif, les données sont stockées sur la pile d'appels. Pour une implémentation itérative, vous pouvez implémenter une pile au sens formel, mais il est possible d'utiliser à la place un tableau simple et relativement petit comme pile de fortune.
Mais les équivalents de pile et de file d'attente peuvent aller beaucoup plus loin que cela. Vous pouvez ajouter des données à un fichier, par exemple, pour une relecture ultérieure. Vous pouvez l'écrire dans un tuyau. Vous pouvez vous le transmettre de manière asynchrone via un réseau de communication.
Si vous voulez devenir fou, vous pouvez même imbriquer des itérations à la place de la récurrence. Cela imposerait une limite supérieure ferme à la taille des tableaux qui pourraient être gérés, mais pas aussi serrée que vous pourriez le penser. Avec un peu de soin et quelques astuces, vous pouvez gérer des tableaux de milliards d'éléments avec un nid de 25 boucles. Un nid aussi profond serait laid et fou, mais néanmoins concevable. Un humain pourrait l'écrire à la main. Et dans ce cas, la série de portées de boucle imbriquées, avec leurs variables de portée de bloc, sert d'équivalent de pile.
La réponse dépend donc de ce que vous entendez exactement par "sans pile":
L'algorithme de sélection @rcgldr n'aidera pas ici car vous l'avez souligné, il est lui-même récursif et très structurellement identique à QuickSort lui-même.
@ john-bollinger J'ai affiné ma question, je suis intéressé par la suppression de la récursivité dans QuickSort mais je suis seulement prêt à payer pour une quantité constante de stockage supplémentaire! Par conséquent, même une pile de taille logarithmique (ou similaire) n'est pas autorisée dans ce cas
@codeR, combien de données prévoyez-vous devoir trier? La différence entre O (log n) et O (1) ne sera probablement pas significative pour vous dans la pratique. Un couple de tableaux auxiliaires de 64 éléments devrait être suffisant pour effectuer un tri rapide d'une entrée de la taille d'un exaoctet sans récursivité.
Mais non, @codeR, bien que vous puissiez réserver une assez petite quantité de stockage fixe qui sera suffisante pour toute entrée que vous pouvez vraisemblablement vous attendre à trier, dans le sens abstrait de l'analyse d'algorithme, le tri rapide nécessite O (log n ) frais généraux. C'est l'un des compromis qui lui permettent d'améliorer ses performances par rapport aux alternatives qui nécessitent O (n ^ 2) étapes pour trier, mais qui n'ont qu'une surcharge O (1).
@JohnBollinger - J'ai supprimé mon commentaire précédent. À mon avis, les boucles imbriquées utiliseraient des variables locales de boucle similaires à une pile de taille fixe, et il existe maintenant une réponse utilisant un tableau de taille fixe qui n'a pas besoin de boucles profondément imbriquées.
@rcgldr, oh oui, je suis d'accord que les boucles imbriquées sont une idée terrible. Le point ici est que bien qu'il existe de nombreuses, nombreuses façons d'implémenter les détails du tri rapide, elles reposent toutes sur une forme de stockage de données structuré qui peut être visualisé sous forme de pile ou de file d'attente.
@JohnBollinger - sauf que comme vous l'avez souligné, la taille de la file d'attente augmente jusqu'à O (n).
En effet, c'est le cas, @rcgldr. Et encore une fois, ce n'est pas le point. Je ne recommande pas d'alternatives à une pile. En effet, mon argument est qu'aucun de ce que j'ai soulevé n'est une alternative de bonne foi . J'évoque une variété d'approches hypothétiques - dont certaines sont mauvaises ou même absurdes - pour observer qu'elles se résument toutes à la même chose à un certain niveau. En outre, il convient peut-être de mentionner que cela vise plus directement la forme originale de la question du PO, qui ne stipulait pas que la quantité de stockage supplémentaire soit O (1).
Le code de la page dans la référence fait une déclaration en gras:
PILE Ma mise en œuvre n'utilise pas la pile pour stocker des données ...
Pourtant, la définition de la fonction comporte de nombreuses variables avec stockage automatique, parmi lesquelles 2 tableaux avec 1000 entrées, qui finiront par utiliser une quantité fixe mais substantielle d'espace de pile:
random: 10000000 elements sorted in 963.973ms sorted: 10000000 elements sorted in 167.621ms reverse sorted: 10000000 elements sorted in 167.375ms constant: 10000000 elements sorted in 9.335ms
Chicaner avec "oui, seule une quantité constante d'espace supplémentaire est nécessaire": bien que cela soit vrai en pratique, c'est parce que la taille de l'entrée à trier est limitée en pratique. Par exemple, le nombre d'électrons dans l'univers, qui n'est pas trop élevé pour être supporté par une quantité raisonnable de stockage supplémentaire.
@JohnBollinger: en effet, nous vivons dans un petit monde.
Apparemment, il est possible d'implémenter un tri rapide non récursif avec seulement une quantité constante d'espace supplémentaire comme indiqué ici . Cela s'appuie sur le travail de Sedgewick pour la formulation non récursive du tri rapide. Au lieu de préserver les valeurs limites (basses et élevées), il effectue essentiellement un balayage linéaire pour déterminer ces limites.
Il nécessite un stockage de données de type pile. Essayez-vous de faire quelque chose avec ces informations?
Quicksort vous oblige à faire une sorte de comptabilité. Si vous utilisez une solution itérative, vous aurez besoin d'une sorte de structure de données de type pile pour garder une trace de vos partitions.
Toute fonction récursive peut être implémentée en tant que fonction itérative. Mais comme @EugeneSh. souligne, vous devrez implémenter quelque chose qui ressemble à une pile.
@EugeneSh. J'étais simplement curieux, car j'ai trouvé une solution non récursive sans pile pour le tri en tas et le tri par fusion.