Discussion :

[Isineac]

Bonjour,

Je cherche un algo permettant de trier des chaînes contenant des nombres.
ATTENTION : les nombres doivent être triés en tant que nombres et pas caractères numériques :
En gros ce serait pour reconstituer le tri de l'explorateur sous Windows XP.

Un exemple de chaînes à trier :
Dossier toto (2)
Dossier toto (10)
Dossier toto (1)

Le résultat à obtenir :
Dossier toto (1)
Dossier toto (2)
Dossier toto (10)

et non pas
Dossier toto (1)
Dossier toto (10)
Dossier toto (2)

Rq : Je ne sais pas si la chaîne comporte des nombres, je ne connais pas leur emplacement etc...
Le tri en lui même, il n'y a pas de problèmes, c'est trouver la formule pour calculer la chaîne correcte qui me pose problèmes.

Merci de votre aide précisieuse.

[pseudocode]

Dans le cas que tu montres, c'est assez simple: tu tries les chaînes en fonction de leurs longueurs (=nombre de caractères), et si elles ont la même longueur tu tries par ordre lexicographique (=comparaison standard de chaînes).

[Isineac]

Oula !!!
Ce n'est pas si simple, les chaînes sont quelconques.
Allez je me m'étais égaré à faire un exemple facile, compliquons un tout petit peu la chose :

à trier :
toto200est_une_chaine
toto199est_court
toto198est_par_contre_super_long
toto32_et_5_comporte_deux nombres
toto32_et_10_comporte_deux_nombres
toto32_et_00006_comporte_deux_nombres

donne :
toto32_et_5_comporte_deux nombres
toto32_et_00006_comporte_deux_nombres
toto32_et_10_comporte_deux_nombres
toto198est_par_contre_super_long
toto199est_court
toto200est_une_chaine

Pour info, créez les répertoires comme ci-dessus, vous verrez, Windows XP les classes comme je veux... Il est terrible ce XP ^^

Dans ma recherche j'ai essayé de transformer la chaine en un nombre de la manière suivante :
"AB" est transformé en 6566
"10" est transformé en 10
...
AB245C serait donc transformé en 656624567
mais ça ne marche pas, A65A serait égal à AAA (656565)
par contre A2B serait bien trié par rapport à A10B (65266 < 651066)

[pseudocode]

Ah... c'est sur que c'est plus compliqué.

Il faudrait séparer ta chaine en groupes de caracteres alpha et numeriques et ensuite comparer groupe par groupe suivant tes règles de tris:
- comparaison de 2 groupes alpha : ordre lexico
- comparaison de 2 groupes numeriques : conversion + ordre naturel
- comparaison alpha / numérique : a toi de voir

phrase #1 : [toto][198][est_par_contre_super_long]
phrase #2 : [toto][32][_et_][5][_][comporte_deux nombres]

Comparaison groupe 1
[toto] / [toto] -> identique

Comparaison groupe 2
[198] / [32] -> 32<198 -> phrase #2 avant phrase #1

[Isineac]

Effectivement ça va marcher...
Il faut implémenter la comparaison de 2 lignes en décomposant groupes par groupes.
J'aurais préféré transformer les lignes pour lancer un tri classique (le but était une implantation dans des requêtes SQL), mais bon, ça devrait passer quand même...

Merci beaucoup pseudocode !!!

PS : faut faire gaffe à la comparaison "toto" et "123", faut décomposer en [toto] et [][123] donc comparer "toto" à ""

[Jedai]

J'aurais préféré transformer les lignes pour lancer un tri classique (le but était une implantation dans des requêtes SQL), mais bon, ça devrait passer quand même...

Tu pourrais simplement transformer les nombres en séquences de caractères, pour ça il faut que tu connaisses la taille de ton plus grand nombre (pour les faire tous de la même taille), mais ensuite c'est une tâche facile.

--
Jedaï

[phryte]

Salut.

compliquons un tout petit peu la chose

Tu peux extraire tous les nombres, par chaîne, dans une matrice puis les trier :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
clear
texte=' toto200est_une_chaine toto199est_court toto32est_par_contre_super_long';
texte=[texte ' toto32_et_5_comporte_deux_nombres toto32_et10_comporte_deux_nombres '];
d=1; 
nb=1;k=0;
for n=1:length(texte)
 if texte(n)==' '  
 v=texte(d:n-1);
 d=n+1;k=0;motx='';rang=0;  
      for i=1:length(v)
         if double(v(i)) > 47 & double(v(i)) < 58
           motx=[motx v(i)];
           rang=1;
         else
         if rang == 1 
           k=k+1;
           rang=0;
           motc(nb,k)=str2num(motx);
           motx='';
         end
       end
       if i == length(v)
        nb=nb+1;
      end
    end
  end
end
motc
%TRI
...

Résultat :
motc =

200 0
199 0
32 0
32 5
32 10

[Graffito]

Tu pourrais simplement transformer les nombres en séquences de caractères, pour ça il faut que tu connaisses la taille de ton plus grand nombre (pour les faire tous de la même taille), mais ensuite c'est une tâche facile.

+1, cadrer les nombres à droite sur la taille max avec des zéros initiaux.

[Jedai]

+1, cadrer les nombres à droite sur la taille max avec des zéros initiaux.

Je pensais à quelque chose de plus efficace en transformant 65 en "\0\0\0A" par exemple.

--
Jedaï

[Graffito]

65 en "\0\0\0A" par exemple

[pseudocode]

chr(65) = A

65 --expand--> short[] { 0, 0, 0, 65 } --cast--> char[] {\0, \0, \0, 'A' }

[Graffito]

chr(65) = A 65 --expand--> short[] { 0, 0, 0, 65 } --cast--> char[] {\0, \0, \0, 'A' }

...

[Isineac]

@phryte:

Tu peux extraire tous les nombres, par chaîne, dans une matrice puis les trier :

Merci pour le temps que tu as passé, mais les chaînes non numériques sont à prendre en compte, j'ai pris des exemples de chaînes commancant toutes par 'toto' mais si j'ai aussi une chaîne 'aaaa24935c64d2' elle viendra en premier.

@Jedai, Graffito, pseudocode :
Cadrer à droite (et donc compléter à 0) les entiers dans les chaînes est possible mais à mon avis gourmand et souvent inutile, un autre jeu d'essai :
GTX280
Code : 325648940
d2r2
GTA4
Allons manger 1 chien et 1 chat

Il faut tout parcourir pour élire le plus grand nombre (9 car ici)

Puis transformer le tout en
GTX000000280
Code : 325648940
d000000002r000000002
GTA000000004
Allons manger 000000001 chien et 000000001 chat

Pour ensuite lancer le tri standard. Ca m'a l'air long...

On peut éventuellement optimiser le calcul des tailles maxi des nombres en uniformisant les nombres commençant au même indice dans les chaînes : on met dans un tableau les indices de départ et la taille maxi, on transforme ensuite.

Ca donnerait après transformation :
GTX280
Code : 325648940
d2r002
GTA004
Allons manger 1 chien et 1 chat


La comparaison par 'groupes' initialement proposée par pseudocode se limitera à comparer les chaînes initiales [GTX] [Code : ] [d] [GTA] et [Allons manger ]
Cette solution m'a l'air plus rapide, la mise en place est simple, j'ai des tri à bulles pour lesquels on peut paramétrer les comparaisons unitaires.

PS : Je rapelle que le but final est de reconstituer le tri façon Explorer XP, donc n'importe quelle chaîne est possible.

[phryte]

Salut.

j'ai aussi une chaîne 'aaaa24935c64d2'

Je ne comprends pas ta remarque. Cette chaîne marche aussi !

Code :

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

1
2
texte=' toto200est_une_chaine toto199est_court toto32est_par_contre_super_long';
texte=[texte ' toto32_et_5_comporte_deux_nombres toto32_et10_comporte_deux_nombres aaaa24935c64d2 '];

Résultat :
motc =

200 0
199 0
32 0
32 5
32 10
24935 64