J'essaie d'améliorer mon C ++ en créant un programme qui prendra une grande quantité de chiffres compris entre 1 et 10 ^ 6. Les godets qui stockeront les chiffres dans chaque passe sont un tableau de nœuds (où le nœud est une structure que j'ai créée contenant une valeur et un attribut de noeud suivant).
Après avoir tri des chiffres en seaux en fonction de la valeur la moins significative, j'ai la fin d'un point de seau sur le début d'un autre seau (afin que je puisse obtenir rapidement les chiffres stockés sans perturber la commande). Mon code n'a pas d'erreur (compiler ou exécuter), mais j'ai frappé un mur de la manière dont je vais résoudre les 6 itérations restantes (puisque je connais la gamme de chiffres).
Le problème que j'ai d'avoir est que les chiffres ont été fournis dans la fonction RadixSort sous la forme d'un tableau INT. Après la première itération du tri, les chiffres sont maintenant stockés dans le tableau des structures. Y a-t-il une façon de pouvoir retravailler mon code de sorte que je n'en ai qu'un pour la boucle pour les 7 itérations, ou j'aurai-je besoin d'une pour la boucle qui s'exécutera une fois et une autre boucle en dessous de celle-ci qui va courir 6 fois avant de retourner le tri total liste?
3 Réponses :
Je pense que vous surchargez gravement votre solution. Vous pouvez implémenter Radix à l'aide du tableau unique reçu dans l'entrée, avec les godets de chaque étape représentés par un réseau d'indices qui marquent l'index de démarrage de chaque godet dans la matrice d'entrée.
En fait, vous pourriez même le faire récursivement. : bien sûr avec cela, il vous suffit d'appeler godets [i + 1] - Les godets [i] provoqueront un débordement de mémoire tampon lorsque i est 9, mais j'ai omis l'amour du chèque supplémentaire ou de la lisibilité; Je pense que vous savez comment gérer cela. RADIXSORT (testées, tailleOf (testées) / tailleOf (testées [0]), 0) et votre tableau doit être trié.
Je ne suis pas sûr, mais la façon dont je comprends, vous ne serez pas dans chaque étape de récursivité, seul l'un des seaux à l'étape précédente. Au fur et à mesure que vous commencez avec le moins important, cela signifie que vous les aurez triés de moins importants à la plupart significatifs, en raison de la restriction au seau dans l'appel récursif. Je me trompe là-bas?
Je ne comprends pas complètement ce que votre question est la suivante: l'algorithme ci-dessus est d'abord de la profondeur, en ce sens que le deuxième godet créé dans le premier appel récursif (tri du chiffre le moins important) ne commencera que pour être trié une fois que le premier godet a été trié complètement (jusqu'au chiffre le plus important). Et oui, le tri Radix fonctionne lorsque vous passez du chiffre le plus important sur le moins important.
Étant donné que vos valeurs sont INTS dans la plage de 0 ... 1 000 000
Vous pouvez créer un ensemble INT de taille 1 000 001 et faire tout ce qui est en deux passes
init le deuxième tableau à tous les zéros.
Créez une passe dans votre réseau d'entrée et utilisez la valeur comme indice d'indice. pour incrémenter la valeur dans le deuxième tableau.
Une fois que vous le faites, le deuxième passage est facile. marcher à travers le deuxième tableau et chaque élément vous dit combien de fois que nombre est apparu dans le tableau d'origine. Utiliser ces informations pour repeupler votre tableau d'entrée.
Supposons donc que votre taille de matrice d'entrée soit 10. Vous allez utiliser 32 Mo (en supposant que 32 bits INTS) pour le trier? FYI, ce que vous avez décrit est Radix Trier avec un radix 64 bits. L'un des défis de la tri radiologique est de choisir un radix approprié qui n'utilise pas trop d'espace. 8 bits n'est pas rare, mais même un radix 16 bits prendrait 2 ^ 16 * Taille de taille (int) = 256kb pour le stockage auxiliaire.
Je crois que cela s'appelle Compter Trier.
Pour accélérer le processus avec une meilleure gestion de la mémoire, créez une matrice pour les comptes qui sont convertis en indices en effectuant une seule passe sur la matrice. Allouer une deuxième matrice Temp Temp de la même taille que le tableau d'origine et le tri analysé entre les deux tableaux jusqu'à ce que la matrice soit triée. Si un nombre impair de passage de tri radix est effectué, le tableau TEMP doit être copié à la matrice d'origine à la fin.
Pour accélérer davantage le processus, utilisez la base 256 au lieu de la base 10 pour le tri radix . Cela ne prend que 1 passe de numérisation pour créer la matrice et 4 passes de tri radix pour faire le tri. Exemple de code:
Pas d'infraction, mais votre code ressemble à un bon exemple comment faire des choses simples compliquées ;-)