RIEN RIEN RIEN RIEN RIEN RIEN RIEN RIEN RIEN RIEN RIEN RIEN RIEN RIEN RIEN RIEN
DRJEROME
Messages postés
436
Date d'inscription
jeudi 9 janvier 2003
Statut
Membre
Dernière intervention
5 février 2015
-
16 nov. 2005 à 18:10
cs_cantador Messages postés 4720 Date d'inscription dimanche 26 février 2006 Statut Modérateur Dernière intervention 31 juillet 2021 - 3 sept. 2006 à 21:56
cs_cantador Messages postés 4720 Date d'inscription dimanche 26 février 2006 Statut Modérateur Dernière intervention 31 juillet 2021 - 3 sept. 2006 à 21:56
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/34509-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien
https://codes-sources.commentcamarche.net/source/34509-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien-rien
3 sept. 2006 à 21:56
var
Form1: TForm1;
tab1, tab2: array of integer;
implementation
uses sorts, Math;
{$R *.dfm}
function TForm1.SGCompare(i, j: Integer): Integer;
var
N1, N2: Integer;
begin
N1 := tab1[i];
N2 := tab1[j];
if N1 > N2 then
Result := -1
else if N1 < N2 then
Result := 1
else
Result := 0;
end;
procedure TForm1.SGExchange(i, j: Integer);
var
T0, T1: integer;
begin
{>> Echange des nombres }
T0 := tab1[i];
T1 := tab2[i];
tab1[i] := tab1[j];
tab2[i] := tab2[j];
tab1[j] := T0;
tab2[j] := T1;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
i: integer;
begin
setlength(tab1, 10);
setlength(tab2, 10);
for i := 0 to 9 do
begin
tab1[i] := randomrange(50, 300);
tab2[i] := 2 * i + 25;
end;
with TQuickSort.Create(SGcompare, SGExchange) do
SortAndFree(0, 9);
end;
2 sept. 2006 à 17:20
Ou tu utilises un "array of record", qui serait plus simple.
C'est l'avantage même de ma méthode qui permet de trier peu importe la structuration des données (je fais bien ma pub, hein ?)
2 sept. 2006 à 16:45
L'idéal, maintenant serait de pouvoir créer deux tableaux statiques de même longueur bien sûr, de lancer un tri croissant ou décroissant sur le premier et de lire le résultat de la nouvelle série nouvellement ordonnée avec une simple boucle sur le deuxième tableau.(en abandonnant le stringgrid..)
cantador
31 août 2006 à 23:39
Voir le descriptif pour savoir ce qui a changé
7 déc. 2005 à 18:48
Voir la liste des MAJ pour plus d'infos.
Et si vous truvez une réponse au fait que ShearSort soit moins rapide que QuickSort, laissez un commentaire.
++ Flo
6 déc. 2005 à 18:36
et http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html.
Pour plus d'infos générales sur les tris, voir ici : http://en.wikipedia.org/wiki/Sort_algorithm
Je suis particulièrement interressé par le "Shear Sort" (2ème lien) : si je peux, je posterai une inplémentation du même type que celle-ci.
Voila, tout cela pour dire que le "classique" si j'ose dire QuickSort n'est pas si quick que ça !
++
5 déc. 2005 à 20:15
j'avais tenter un pseudo-algo pour trier des nombres en PHP (rien a voir) le probleme c'est que mon algo avais un fonctionnement plus que lourdingue, en gros pour chaque nouveau chiffre present dans un tableau je rechercher le plus petit ou identique pour l'indexer.
probleme, plus il y avait de chiffre et plus la routine devenez lente de façon exponentielle (lol). en local passe encore, mais sur un serveur ce n'etait pas vraiment adapté ni acceptable donc abandon de ce truc immonde.
ton quicksort je vais me l'adapter en php car il vas bien me servir.
je pense qu'il est suffisament performant et rapide pour traiter pas mal d'entrées (aprés tout y'en a pas 150 milliard non plus ...)
AlphaSort a l'air plutot pas mal aussi, j'ai meme ete etonné de voir qu'il avait ete ecrit en TP7 sur des bon vieux 386/486 ... ça faisait longtemps et merci a Florenth de nous rapeller a quel point on a vieillis :p
je remercie tout les intervenants egalement pour les divers liens et comme l'a dit DelphiProg debat passionant et enrichissant.
20 nov. 2005 à 11:43
J'ai aussi un lien à proposer : http://fr.wikipedia.org/wiki/Algorithme_de_tri
Voir notamment le mémoire de synthèse réalisé par Nicolas HERVE.
Cette discussion est passionnante, vraiment passionnante et riche d'enseignements.
20 nov. 2005 à 09:50
Mais je n'avais pas envie de poster un commentaire tout riquiqui au sujet du transtypage. ^^
Alain proviste à raison: suivant les données à traiter, il existe d'autres algo qui sont plus performants que le QuickSort: A-Sort.
Voir ici: http://perso.wanadoo.fr/ldelafosse/Sort/Papers/Asort.htm
Mais cela consomme plus de mémoire.
A voir ...
20 nov. 2005 à 08:40
Qui est sur les nerfs ? Je n'ai pas eu cette impression ici. Bien au contraire. Le débat est à la hauteur de la qualité du code soumis par Florenth. C'est plus un discours de passionnés que de gens énervés. Mais tu as eu raison de faire cette remarque.
Alain Proviste a écrit : "l'efficacité des tris dépend en grande partie des éléments à trier n'est-ce pas ?"
Pourrais-tu développer un peu plus, stp ?
20 nov. 2005 à 01:42
La plaisanterie devient de plus en plus dure à faire passer ici. Merci de lire jusqu'au bout de la ligne (2 fois s'il le faut) pour bien comprendre le message. Vous êtes trop sur les nerfs, décrochez un peut ça fait du bien ;-)
Il est évident que Quick Sort est le plus rapide des trois c'est sans appel.
DelphiProg > tu penses bien que j'ai fait le teste depuis longtemps (j'utilise Quick Sort depuis mes début en Turbo Pascal) et pour finir merci pour ce lien très instructif.
Stay Cool :-)
@+
Cirec
19 nov. 2005 à 21:47
par exemple le quicksort est très efficace quand l'ecart-type est faible mais moins efficace que d'autres dans d'autres conditions ?
19 nov. 2005 à 21:26
Pourquoi vouloir implémenter d'autres algorithmes ici quand on sait d'avance qu'ils seront moins performants ?
Non, ton code est trop bien, n'y touche surtout pas.
Pour finir : un peu de théorie sur les algorithmes de tri ?
http://tinyurl.com/cftmb
19 nov. 2005 à 20:56
Evidemment je ne vais pas le faire : pourquoi s'embetter à creer un descendant de cette classe alors qu'il est si simple d'utiliser les procedures QuickSort().
++
19 nov. 2005 à 20:39
En effet, le transtypage est explicitement fait par Delphi. On peut donc l'ommetre et alleger le code.
Je ne compte pas implémenter le SelectionSort et encore moins le BubbleSort. Le but de ce code est de pouvoir implémenter un algorithme de tri performant (le QuickSort, mais il en existe d'autres) aussi simplement que le classique :
var
i, j, Petit: Integer;
begin
for i := Min to Max do
begin
Petit := i;
for j := i + 1 to Max -1 do
if Array[j] < Array[Petit] then
Petit := j;
{ Invesement de Array[Petit] avec Array[i]. }
end;
end;
Cette méthode, simpliste à implémenter est bien plus longue à l'execution.
Le QuickSort est rapide mais difficile à implémenter.
Cette source présente le QuickSort avec tous ses avantages mais sans ses inconvénients !!
++
19 nov. 2005 à 14:09
j'ai vu l'exemple SortThreads que l'on trouve dans DELPHI et ton code
et ben good job
je note 10/10
Bravo
Juste pour information tu dis :
{ CompareValue() renvoie un TValueRelationShip qui est transtypé en Integer. }
Result := Integer(CompareValue(FArray[Item1], FArray[Item2]));
je pense que le transtypage n'est pas utile vue les déclarations suivantes: (tiré de l'unité Math)
type
TValueRelationship = -1..1;
const
LessThanValue = Low(TValueRelationship);
EqualsValue = 0;
GreaterThanValue = High(TValueRelationship);
donc 3 valeurs possibles de type Integer:
le résultat de CompareValue est soit:
LessThanValue = -1
EqualsValue = 0
GreaterThanValue = 1
on peut donc remplacer:
Result := Integer(CompareValue(FArray[Item1], FArray[Item2]));
par:
Result := CompareValue(FArray[Item1], FArray[Item2]);
Comme tu as l'aire d'être bien lancé il ne reste plus qu'à implémenter
les deux autres methodes de tries (TBubbleSort, TSelectionSort) de l'exemple ;-)
@+
Cirec
18 nov. 2005 à 23:06
Tu as écrit : "4- à créer une classe qui peut être dérivée pour prendre en charge des cas spécifiques qui reviennent souvent (array of Integer par exemple)"
Je pense que ce serait une erreur car tu te détournerais de ton objectif principal et premier, et cela ferait double emploi avec une construction déjà en mesure de prendre en charge ce type de données.
18 nov. 2005 à 18:26
J'ai pris ce code de l'exemple SortThreads que l'on trouve dnas (DELPHI)\Exemples\Threads\
La seule difficulté ce sont ces quelque lignes rajoutées:
{ Change l'index du "milieu" s'il est égal à Lo ou Hi. }
if Mid = Lo then
Mid := Hi
else if Mid = Hi then
Mid := Lo;
C'est pas spécialement évident à trouver ...
Mais en dehors de ça, pas de quoi couper trois pattes à un canard comme on dit !!
18 nov. 2005 à 18:19
Delphiprog > Merci pour tout.
En effet, je ferais mieux de déclarer les classes dans la partie implémentation. Mais au fait, je ne savais même pas qu'on pouvait le faire ! Une mise à jout s'impose.
Mais sans vouloir vanter mon code, je peux rajouter un
4 - à créer une classe qui peut être dérivée pour prendre en charge des cas spécifiques qui reviennent souvent (array of Integer par exemple).
@ ++ Flo
18 nov. 2005 à 16:34
Tu as réussi :
1 - l'encapsulation de l'algorithme QuickSort qui n'est pas évident à mettre en oeuvre (surtout quand on est pressé).
2 - à dissocier l'algorithme de tri des méthodes de classement et de permutation, ce qui permet une souplesse de réutilisation à l'infini
3 - à atteindre un niveau d'abstraction tel que les mêmes fonctions peuvent aussi bien traiter des chaines que des entiers ou toute autre entité pouvant faire l'objet d'un classement.
Pour toutes ces raisons, moi je dis chapeau bas.
J'aurai juste une petite suggestion : pourquoi exposer les classes TQuickSort et descendants à l'extérieur alors que ce n'est pas utile ? Tu ferais mieux de les déclarer dans la partie implémentation.
Pour toutes ces raisons, ton travail mériterait un 20/10. Mais je ne mettrai que 10/10 ;o)
16 nov. 2005 à 18:13
c'est mon doigt qui n'a pas appuyé assez fort ;)
16 nov. 2005 à 18:10
Sinon ça devrait aller ;)