TRIER (AVEC QUICKSORT ) ET AFFICHER TOUS LES TABLEAUX ET PLUS ENCORE
WhiteHippo
Messages postés
1154
Date d'inscription
samedi 14 août 2004
Statut
Membre
Dernière intervention
5 avril 2012
-
14 déc. 2005 à 23:12
cs_Forman Messages postés 600 Date d'inscription samedi 8 juin 2002 Statut Membre Dernière intervention 6 avril 2010 - 21 nov. 2006 à 15:06
cs_Forman Messages postés 600 Date d'inscription samedi 8 juin 2002 Statut Membre Dernière intervention 6 avril 2010 - 21 nov. 2006 à 15:06
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/35092-trier-avec-quicksort-et-afficher-tous-les-tableaux-et-plus-encore
https://codes-sources.commentcamarche.net/source/35092-trier-avec-quicksort-et-afficher-tous-les-tableaux-et-plus-encore
21 nov. 2006 à 15:06
TCompareProc=function(Index1,Index2:Integer):Boolean;
TExchangeProc=procedure(Index1,Index2:Integer);
Dans ces conditions, on peut imaginer une déclaration de QuickSort ainsi:
procedure QuickSort(IsInferior:TCompareProc;Exchange:TExchangeProc;const IndexMin,IndexMan:Integer);
Avec cette déclaration, on peut trier n'importe quelle structure de donnée indexée par des entiers en fonction de n'importe quelle relation d'ordre. Après tout, la méthode du QuickSort ne demande qu'à connaître la façon de comparer les données à 2 index donnés, et à savoir les inverser dans leurs "cases" respectives pour fonctionner...
19 déc. 2005 à 15:46
Il n'est donc pas possible d'en creer une version "universelle".
Ex: pour les strings, il les classe suivant leur premioère lettre dna sun tableau du genre ['A'..'Z'] et il reclasse chaque case du tableau (qui est en fait un sous tableau) en fonction de la deuxième lettre cette fois. Et ainsi de suite pour toutes les lettres. (en gros, je simplifie drolement là ...)
Ensuite, il replace les strings dans leur tableau d'origine et voila ! On voit ici que la méthode consomme bien plus de mémoire mais peut se révéler plus efficace.
A voir ...
Mais telle que j'ai implémenté la classe TSort, il est impossible de concevoir ce genre de tri; l faudrait la modifier.
++
19 déc. 2005 à 12:49
et avec cirec, oui j'ai pensé en effet au TBaseArray ou TCustomArray de MxArrays ...
mais cette unité n'est disponible que dans la version Entreprise de Delphi
puisqu'elle fait partie de Decision Cube (logiquement non present dans les versions PLE).
Par contre pour vous deux, qu'en est t'il de l'algo ASort ?
je suis etonné que vous n'ayez pas encore rien sortis sur cette methode. (pas le temps ?)
19 déc. 2005 à 11:39
Soit la tienne où la mienne alors faite votre choix...
où alors encore utiliser à la place d'un array normal un TCustomArray de l'unité MxArrays qui lui intègre le trie mais bon tout ça c'est affaire de goût, de préférence personnel et autres que l'on peut pas cités ici ^_^
@+
Cirec
19 déc. 2005 à 11:20
Ou un TObjectList.
Mais non, le résultat ne sera pas basé sur la valeur hexa de l'adresse mémoire (heureusement) car tu fournis une méthode de comparaison.
Trie la liste, en employant l'algorithme Tri Rapide (QuickSort) et en utilisant Compare comme fonction de comparaison.
Aide de Delphi sur TList.Sort :
type TListSortCompare = function (Item1, Item2: Pointer): Integer;
procedure Sort(Compare: TListSortCompare);
Description
La méthode Sort permet de trier les éléments du tableau Items. Compare est une fonction de comparaison indiquant comment les éléments sont ordonnés. Compare renvoie < 0 si Item1 est inférieur à Item2, 0 s'ils sont égaux et > 0 si Item1 est supérieur à Item2.
____________________
C'est donc une méthode efficace. Mais si tu as un array[0..25] of string, tu ne vas pas t'amuser à remplir un TList avec les éléments du tableau pour pouvoir utiliser la métrhode Sort et ensuite tout remetre dans le tableau (avec toutes les manipulaitons de pointeurs que ça implique).
C'est pour cela qu'il vauts mieux utiliser des méthodes "universelles" telle que la mienne ou celle de Cirec. Après, quand au choix entre ces deux méthodes, j'ai promis de ne plus rien dire; fais ton choix.
++
19 déc. 2005 à 04:05
pourquoi ne pas simplement utiliser une TList et jouer avec sa procedure .SORT (quicksort) ... ?
ce serait plus rapide et de plus vus que c'est une liste de pointeurs elle accepteras n'importe quel types ...
ah oui mais problemes, c'est le resultat du tris qui serat basé sur la valeur hexa et non sur la valeur du type...
qu'en pensez vous tout les deux ?
18 déc. 2005 à 10:01
comme tu le dis florenth le Pascal est fortement typé ce qui rend l'ecriture de ce genre de methode fastidieuse et complexe. donc beaucoup de problemes a relever et beaucoup de code tester avant de trouver une solution.
17 déc. 2005 à 12:37
Pour le cas des types tableaux, f0xi s'est sûrement mieux exprimé que moi.
Par contre, pour ce qui est des Array = array of const (ou array of TVarRec) je suis potentiellement contre. Premierement parce que cela a été inventé pour passer une nombre inconnu de parametres de types inconnus (en tout cas, non renseignés) et non pour un tableau d'un même type.
Si on commence à se servir de ces types spéciaux (TVarRec, type indeterminé, ...) on se rapproche du C++ que je conteste tant.
Le langage Pascal est réputé pour être fortement typé et dès que l'on commence à vouloir y echapper, le précieux compilateur ne fait plus les vérifications tant utiles et on obtient des erreurs de compilation (quand c'est pas trop grave) ou des débordements de mémoire quasiment impossibles à cerner. Et ça, je n'en veut point.
Donc, de ce côté là, je préfère le code de cirec à celui que propose f0xi (après le mien evidemment ^^).
Bon, j'arrete de troller, ça ne sert à rien.
Si vous avez des problèmes de prog', il reste le forum.
@ bientôt j'espère.
16 déc. 2005 à 23:12
const aArray : array of const
Le premier tableau que j'essaye de lui passé il me dit type incompatible et copy(aArray,FromIndex,ToIndex) me fait également une erreur
Donc résultat je ne comprend plus je voudrais bien changer, améliorer en fonction de vos remarques mais ça ne fonctionne pas :(
Cette fois c'est moi qui demande un éclaircissement
la balle est dans votre camp ^_^
@+
Cirec
16 déc. 2005 à 22:32
donc pas de soucis c'est normal.
bon pour le reste il faut que je regarde ça de plus près
@+
Cirec
16 déc. 2005 à 22:25
bon j'ai pas trop fait d'investigation dans vos deux sources respectives mais si il y'a une chose a relever :
declarer des types tableaux predefinis (array[0..N] of truc) c'est souvent inutile car souvent on en voudras moins ou plus ou pas du tout...
donc se basé completement sur du tableaux dynamique, meme si ces derniers necessite un traitement fastidieux (setlength et tout ça).
mais je rejoins Florenth la dessus, ce que tu est en train de faire c'est un peu comme si tu voulais declarer toute les matrices possible qu'on peu faire en delphi jusqu'a ce qu'on en ai marre... c'est bien ... mais c'est beaucoup de travail pour rien en fait...
pour la variable non typée, je retiens surtout la remarque de Florenth tout en me basant sur ma propre experience.
aArray auray (oops > aurait) pus etre meme declaré comme cela :
const aArray : array of const
ce qui permet de passer n'importe quoi comme type de tableau et meme de contenus mitigés ce qui pourrait etre au final bien plus interressant. (regarder le code de la fonction WideFormatBuf dans l'unité SysUtils pour voir comment les dev de chez borland traite un array of const > Asm c'est du costaud...)
fonction(tableaudentier ...)
fonction([1,2,3,'a','chien','chat',false] ...)
mais la heu ... impossible de trier ce bordel innomable quoique...
mais bon, utiliser que du Dyn ça supprimerais pas mal de lignes de codes et ce serait bien plus simple.
en plus, pour en revenir a Array : array of const, c'est que tu pourrais meme utiliser format directement pour sortir le tableau en string :
Function WriteArray(Const aArray : array of const; const FromIndex,ToIndex: Integer): String;
begin
Result := Format( DupeString('%s',abs(ToIndex-FromIndex)), copy(aArray,FromIndex,ToIndex));
end;
(a tester)
par contre j'ai remarquer (sauf erreur d'utilisation de ma part) que le fonctionnement de ton logiciel ete un peu etrange.
exemple je rentre : 1 2 3 4 5 6 7 dans le memo je click sur créer puis trier et pouf j'ai des nouvelles valeurs ... la je change le type et pouf ... de nouvelles valeurs encore...
je crois ne pas avoir tout saisis mais il me semble que logiquement il ne devrait pas faire cela.
eclaircicement ?
16 déc. 2005 à 21:04
Etonnant non ? Compte tenu des déclarations que tu as faites "Mais ton code, même s'il présente l'avantage de ne pas réécrire les méthodes de tri est cependant très lourd" donc il y a comme un souci dans ce que tu dis ^-^.
La méthode que j'utilise est identique à:
Function(Var aArray : Array[0..10]of Integer); et
Function(Var aArray : Array of Integer); à ceci près que la mienne accepte les deux type d'array et autres (Ex array of String, of Double, TMemo, TStrings ...)
En claire il n'y a pas de re-déclaration de tableau quand le trie est exécuté comme tu le penses, le Tableau est passé en paramètre inconnu certes mais à aucun moment je ne re-déclare ce dernier pour avoir accès aux informations qu'il contient
Teste et regarde l'occupation mémoire et tu seras peut être surpris du résultat.
Si non il faudra que tu m'explique comment ta source et la mienne consomme (à peut de chose près) la même quantité de mémoire. Il y a comme un os ^_^
@+
Cirec
16 déc. 2005 à 19:14
Celui qui dirait le contraire serait hypocrite.
Mais ton code, même s'il présente l'avantage de ne pas réécrire les méthodes de tri est cependant très lourd. Une unité si lourde que cela pour économiser à peine 20 lignes d'un code élémentaire, je trouve ça peu correct. Mais je respecte ton travail.
Le seul truc interessant, c'est l'utilisation d'une variable non typée. J'ai longuement hésité à en mettre et j'ai dit non. Pour une raison simple: si on a besoin d'avoir un acces à une variable (ici le tableau mais il peut y avoir d'autres choses) et que l'on doit se résoudre à cette méthode (celle du type indéfini) c'est que l'on a mal organisé ses classes et toutes la structure du programme.
Je ne dis pas cela pour rabaisser qui que ce soit, mais je trouve la notion de classe tellement importante (et surtout très pratique) que maintenant, je fais super attention à tous ce genre de détails. Pas une ligne de code supperflue, pas un parametre à une fonction supperflu non plus.
Pour la question de l'occupation mémoire, je suis tout à fait d'accord. Mais je ne parlais pas de cela. Si on veut utiliser ta méthode, on est obligé de déclarer un TIntArray qui une fois utlisé, prend plein de mémoire alors que peut être un array[0..12] of Integer suffirait largement.
C'est cela que je voulais dire. Mais tu vas dire qu'on peut utiliser un tableau dynamique ? Oui mais là, tu consomme 2 lignes pour l'allouer et de libérer alors bon ... au final on est plus trop gagnant en terme du nombre de lignes.
Tout cela pour dire que c'est aux autres de juger, de faire leur choix. Je dirais que ceux qui cherchent une solution pour intégrer un tri dans leurs classes ou autres (c'est mon cas) choisiront ma solution. Les autres préfèreront peut être la tienne.
Mais mon code avait quand même pour but d'atteindre un niveau d'abstration pour pouvior trier n'importe quoi alors que toi, là, tu vas êtte obligé de modifier ton unité, ta procédure Arrayquicksort() et autres pour pouvoir implémenter un tri sur autre chose que ce que tu as initialement prévu.
Mais c'est ton choix ...
++ Florent
16 déc. 2005 à 17:08
Maintenant je comprend très bien que l'on préfère sa source à celle des autres ce qui est légitime mais je ne suis pas certain que tes arguments pèsent très lourd dans la balance ^_^
et je le répète pour les autres l'intérêt de cette source c'est qu'elle accepte tout, tableaux, Memo, TStrings, en paramètre et si votre bonheur ne s'y trouvait pas il suffit de le déclarer une fois pour toute
Voilà amicalement
Cirec
16 déc. 2005 à 16:45
Case Kind of
vtInteger : if Dynamique Then aL := Low(TDynIntArray(aArray)) Else
aL := Low(TIntArray(aArray));
...
...
End;
Et ensuite seulement
For i := aL to ...
Alors que moi je n'ais qu'une seul boucle pour le tout ^_^
Teste, regarde, scrute la source livrée en exemple et tu comprendras le pourquoi du comment ^_^
Si non pour count à la place de size je suis entièrement d'accord avec toi
Je vais faire le nécessaire comme ça plus de doute possible.
@+
Cirec
16 déc. 2005 à 14:21
alors que tu pourrais l'appeler directement dans la methode ...
Size := Length(Array) ou High(Array)
egalement aussi prevoir de ne pas forcement partir de 0 dans le cas ou on utilise un tableau qui ne commence pas a 0 ... Low(Array)
en plus petit point sur cela, ne serait il pas preferable d'appeler le parametre Size > Count
car il s'agit du nombre d'element et non de la "Taille" (sizeof) du tableau.
Size est assé ambigu ...
Count serait plus explicite.
Function WriteArray(Const aArray; Kind: TVarType; FromIndex,
ToIndex: Integer; Const Dynamique: Boolean = False): String;
Var aL,aH,Count : Integer;
Begin
Result := EmptyStr;
aL := Low(aArray);
aH := High(aArray)-1;
If (ToIndex <= aL) or (ToIndex > aH) then ToIndex := aH;
If (FromIndex < aL) Then FromIndex := aL;
If (FromIndex > aH) Then FromIndex := aH;
For Count := FromIndex to ToIndex do ...
ce qui permet l'utilisation de tableau [d>0..e], [d<0..e] ce qui peut etre utile quand on utilise des tableau "[-5..5] of integer" ou "[1..10] of char" par exemple.
en gros l'utilisation de tableaux (dynamique ou non) qui ne parte pas de 0
qu'en pense tu ?
15 déc. 2005 à 13:09
@+
Cirec
15 déc. 2005 à 12:55
Cordialement.
14 déc. 2005 à 23:58
Si non est ce que tu sais si il y a un moyen de déterminer le type de variable passé dans ce genre de procédure où function (Var aArray) j'ai testé plusieurs chose sans succès. Ce qui implique (dans la configuration actuelle) de vérifier la validité des paramètres passé à la procédure où function et de lui donner également le type (vtInteger par Ex). Si tu vois d'autres problèmes où améliorations à apporter sur tout n'hésite pas
@+
Cirec
14 déc. 2005 à 23:31
Merci
@+
Cirec
14 déc. 2005 à 23:12
N.B. D'ailleurs, il ne faut pas oublier que cette astuce a ses failles. Un test simple pour s'en convaincre un appel de aIntArrayExchangeProc avec item1 égal à Item2, ce qui engendra une irrémédiable mise à zéro de la mémoire indexée.
Cordialement.