Discussion :

[Cecilka]

Voilà, tout est dit dans le titre. Je voudrais savoir selon vous quel est le meilleur algorithme pour trier un nombre conséquent de chaînes de caractères (2 à 4 millions, mettons) dans l'ordre lexicographique.
Merci

[Matthieu Brucher]

Tri par fusion, non ?

[ToTo13]

Bonjour,

quel est le taille de tes chaines de caractères ?

Si elles ne sont pas tres longues...
une méthode valable dans cette situation est de trier caractère par caractères :
- Tu choisis un algo de tri (quicksort par exemple) et tu tries tous les mots en ne regardant que le caractère i dans la chaine de caractère.
- Tu répètes cette opération en commencant par la fin du mot pour que le tri fonctionne.
- Il faut juste penser à gérer ne fait que les mots n'ont pas la même taille.

[TanEk]

Si tu ne dois juste que trier, prends le quicksort. Si tu dois trier et garder trier (insérer, enlever des chaînes, etc.) utilises un arbre binaire (mais je ne pense pas que ce soit le cas ici).

[gangsoleil]

Bonjour,

Comme l'ont dit les autres personnes, il faut que tu te bases sur un algo comme quicksort.

Ensuite, tu peux chercher non pas à améliorer l'algo, mais à l'appliquer sur tout ou partie de la chaine.

Par exemple si tes chaines ont de très nombreuses différences dans les premiers caractères, il vaut mieux essayer de trier en se bassant d'abord sur les premier caractères.
En revanche, si tu as des chaines ayant une grande probabilité d'avoir le même début, il ne sera pas intéressant de tester systématiquement tous les caractères en commencant par le début.

Il faut donc que tu cherches des points communs ou des différences à tes chaines, pour pouvoir en tirer des heuristiques, qui te permettront d'améliorer le temps de traitment au final.

[Graffito]

Bonjour,

Pour trier simplement, un algo de sort comme indiqué dans les réponses précédentes.

Par contre, si on doit faire des recherches et des insertions, je préconiserais un arbre comme celui de l'exemple ci-dessous (plutot qu'un arbre binaire) :

Avec les les mots :

• A
• AME
• AMI
• AMOUR
• BUT
• CE

on aurait la structure suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
#
|
A------------B-------C
|            |       |
*-M          U       E
   |         |       |
   E--I--O   T       *
   |  |  |   | 
   *  *  U   *
         |
         R 
         |
         *

Le caractère * indique la fin du mot.