Discussion :

[sbeu]

Bonjour.
Je suis en train de plancher pour trouver un algo optimisé pour trier une grille en delphi sur plusieurs colonnes.
Ma méthode est la suivante:
je trie sur la première colonne (Col=1), puis j'appelle en récursif cette fonction qui trie la colonne Col+1 de IDébut à IFin (De IDébut à IFin, les valeurs de la colonne Col sont identiques)
Est-ce la meilleure méthode?
Merci.

[PINGOUIN_GEANT]

Personnellement, je ne comprends pas tout.
qu'est-ce qu'une grille ? j'ai l'impression que c'est un tableau à deux dimensions.
quels sonts les éléments qui doivent être ordonnés ? doit-on juste pouvoir lire les éléments d'une colonne dans l'ordre ou y-a-t'il d'autres possibilités ? et s'il y en a, un élément dans une colonne doit-il rester cette colonne ?

[sbeu]

Désolé si je me suis mal exprimé. Il s'agit effectivement d'une sorte de tableau de chaînes à deux dimensions.
Je dis grille car je vais utiliser une TStringGrid (composant delphi qui représente un tableau de chaines)
Il faut que la première colonne soit triée, puis, il faut que la seconde soit trié dans le cas où les éléments de la première colonne sont identiques.
Me fais-je comprendre?

[KibitO]

Cela va faire un an que je ne touche plus de Pascal, mais je pense que ça va t'aider :


Exemple pour la premiere colonne :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
 
temp : string;
 
for rang:=1 to n
{
if TStringGrid[1][rang] > TStringGrid[1][rang+1]
{
temp := TStringGrid[1][rang+1];
TStringGrid[1][rang+1] := TStringGrid[1][rang];
TStringGrid[1][rang] := temp;
}
}

[PINGOUIN_GEANT]

Kibito>> ton programme ne trie pas ta colonne et apparamment c'est ce qu'il veut faire.
sbeu>>tu parles que "les éléments de la première colonne sont identiques"
c'est entre eux ou identiques à ceux de la deuxième colonne.
je suppose que c'est la deuxième solution (ou alors as-tu besoin d'un algo de tri ?, mais a priori non vu que tu parles déjà d'une fonction de tri dans le premier)
pour comparer la colonne C1 et C2, à mon avis la meilleure solution dépend du fait si C1 sera souvent égal à C2 ou pas.
si c'est souvent (ou beaucoup d'éléments sont identiques) il vaut sans doute mieux trier puis comparer 1 à 1.
si c'est le contraire, cherche directement pour chaque élément son correspondant dans la liste car tu trouveras rapidement un contre-exemple
je ne quantifie rien en parlant de "souvent" mais à toi de voir.

PS: à noter aussi le problème de gestion des doublons dans la deuxième solution.
et je ne comprends pas ta manière récursive pour arriver à la solution, peux-tu expliquer ?

[plegat]

Bonsoir,
Si j'ai tout bien compris, c'est d'une fonction de tri multi-critères dont il a besoin, pas d'un comparateur de colonnes.

En gros, une procédure pour passer de:

a a b
c a b
a a a
b a a
a c a
d a a
b b c
c a a
a b a

à

a a a
a a b
a b a
a c a
b a a
b b c
c a a
c a b
d a a

On trie sur la première colonne... puis pour chaque plage où les éléments de la première colonne sont les mêmes, on trie sur la seconde... et récursivement.
Normalement, en commençant le tri par la dernière colonne et en remontant vers la première, avec un algo de tri qui traite les lignes de la première vers la dernière, ça devrait passer.

[PINGOUIN_GEANT]

maintenant je pense avoir compris (sinon je )
en gros tu tries suivant un ordre lexicographique.
je vois deux oppositions à un tri en commençant par la dernère colonne:
le coût de calcul peut être très important si le nombre de colonnes est grand car on triera des colonnes inutilement puisque les éléments auraient déjà été à leur place dans un tri direct:
2: Prenons un exemple
trions bel et beu en commençant par la dernière colonne
on aura d'abord
bel
...
beu
mais quand on triera la deuxième colonne on pourra tomber sur
...
beu
bel
....
(en C++ il y a sort et stable_sort)

du coup je pense avoir compris tes appels récursifs.
en tout cas, ta fonction qui trie les éléments des colonnes avec des délimiteurs de début et de fin est très élégante et efficace pour résoudre le problème
et je ne vois pas comment on pourrait réduire le nombre de tris à faire, à mon avis c'est le minimum pour réussir. donc:

edit: en fait ce n'est pas vraiment du récursif car ta fonction tri agit dès la première colonne.

[sbeu]

merci pour vos réponses.
Je vais utiliser la méthode de plégat qui me paraît la méilleure solution.
Question subsidiaire: quelqu'un sait-il si une implémentation de cette méthode (tri col n puis tri sur col n+1 sur les éléments identiques entre eux de la première colonne) existe en Delphi? Bon, si ça n'existe pas, je la coderai, je devrais y arriver...
Encore merci!

[PINGOUIN_GEANT]

Je vais utiliser la méthode de plégat qui me paraît la méilleure solution.

j'ai encore raté qqch donc je et au passage je me
(je fais du deux en un)

[plegat]

Salut,

Je ne sais pas si "ma" méthode est la meilleure... faut voir en fonction de ce que tu veux trier. Pour que ça marche, il faut tourner avec un tri à bulle ou similaire, sinon (comme le dit pingouin_géant) on se retrouve en train de tout remélanger en triant la colonne suivante. Et bon, c'est pas vraiment le tri le plus rapide...

[sbeu]

Je pense qu'un tri rapdie est applicable... Tu fais tri rapide sur la premiere colonne en entier, puis tu fais tri rapide sur colonne deux de la ligne 1 jusqu'à la ligne 10 (par exepmple bien sur, disons que toutes les valeurs de la colonne 1 sont identiques que la ligne 1 à 10)
et etc...