Question pour un champion de maths [Résolu]

Signaler
Messages postés
4716
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
27 mars 2018
-
cs_cantador
Messages postés
4716
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
27 mars 2018
-
Bonjour à tous,

J'ai une liste de données de cette manière :
ex : 7 enregistrements :

           S1     S2

1        10      348
2        45      230
3        89      339
4        12      339
5        142    780
6        7        459
7        548    650

Comment faire pour trier numériquement de façon décroissante la série S2 de nombres et récupérer ensuite la première sans utiliser de table ni SQL et de manière très rapide ?

merci par avance.

cantador

14 réponses

Messages postés
814
Date d'inscription
vendredi 3 novembre 2000
Statut
Membre
Dernière intervention
30 juillet 2009
3
si tu n'as QUE 7 valeur a trier, un trie à bulle est bien assez rapide.


Si tu avais plus de valeur, ca vaudrait la peine de chercher un autre algo.


Mais la plus grosse question est:


Comment stock tu ces "enregistrement"? de quel type sont-il ?


si tu veux optimiser un try, commence par choisir un moyen de stockage
adapté. Le mieux étant un tableau statique et un record d'integer je
pense. à voir.


bon code,
Messages postés
4716
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
27 mars 2018
11
7 c'était juste un exemple, mais en fait  j'ai plus de valeur que çà.
C'est OK pour le tri à bulles..
bien sûr j'ai déjà fait qlqchose, mais ce n'est pas très bon.
un  record d'integer...intéressant..

je te précise que j'ai une totale liberté de stockage des nombres et je voudrais éviter le stockage table ou fichier texte.
Pour simplifier,on va considérer que j'ai  deux tableaux statiques
de 1 à n.
Voilà,  maintenant coment faire pour trier l'un en décroissance et récupérer la liste du deuxième sachant que les positions des nombres dans les deux sont évidemement liées.(tabA(1) en relation 1-1 avec tabB(1)....  tabA(n) avec tabB(n).

merci par avance pour le coup de main.

cantador
Messages postés
4716
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
27 mars 2018
11
Je connaissais déjà le QuickSort..
Mais ce n'est pas mon souci du moment..
Je souhaiterai trier en décroissant le premier tableau.
mais, mais mais mais ..

Comment faire pour que le 2e tableau soit affecté lui aussi par le tri du premier en gardant la relation avec les positions correspondantes.

Bref, un bon schèma valant mieux que..

ex: j'ai 

17   567
  8   728
45   459
             
je trie la première série cela donne :

         45   459
         17   567
           8   728

et je relie ma seconde liste (459, 567, 728)

Je pense que c'est plus clair maintenant.

 
            






cantador
Messages postés
199
Date d'inscription
dimanche 2 mars 2003
Statut
Membre
Dernière intervention
10 octobre 2006
1
Dichotomie.

C'est simple, et il te dit si la valeur existe deja. dans ce cas, il te faut refaire une dichotomie par rapport au 2ème tableau (mais il faut changer les bornes de recherche

Perso je metterai dans une IntegerList (à créer mais c'est facile : descendant du TList en adaptant) parce que tu auras accès au Insert


Voilà, moi je ferais comme ceci :)

Tout problème a sa solution... Mais en général, celle que l'on trouve n'est jamais la bonne...
Messages postés
814
Date d'inscription
vendredi 3 novembre 2000
Statut
Membre
Dernière intervention
30 juillet 2009
3
tu évite de faire deux tableau si tu veux qqch de rapide. il te faut regrouper tes valeurs dans un seul type.

note que le type integer est le plus rapide a gerer pour ton pc (plus rapide que byte malgré que byte soit plus petit)

La source de florent devrait repondre à toute tes question.


mais si tu veux un exemple de principe, tu peux déclare un truc genre

TUneDonne = record
s1 : integer;
s2 : integer;
end;

TTabDonnes : array[1..n] of TuneDonne;


function EstAvant (d1, d2 : TUneDonne) : boolean;
begin
// cette methode definit l'ordre de tri.
result := D1.S1 < D2.S1;

end;


et ensuite tu reprend un code d'exemple de tri, en remplacer la comparaison

"tab[i] > tab[1+1]" par la tienne


"EstAvant(tab[i], tab[i+1])"


c'est plus clair comme ça?


jete aussi un oeil sur les pointeur de function (aussi appeler type function). Cela te permet d'avoir un seul code et de changer le critère de trie très très facilement.


je te recommande de coder ton trie dans une unité a part afin de pouvoir changer facilement l'implementation par la suite.

bon code,
Messages postés
4716
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
27 mars 2018
11
Je ne peux pas encore valider car je ne suis pas sûr que cela répond à mon souci.
Dans l'attente, merci pour votre aide.
A bientôt.

cantador
Messages postés
1023
Date d'inscription
dimanche 1 août 2004
Statut
Membre
Dernière intervention
17 août 2008

Ben, oui, ma source foncitonne parfaitement bien et répond à ton problème.
Faut lire avant de parler !

type
TMonType = record
S1, S2: Integer;
end;

var
MonTab: array of TMonType;

function TForm1.Arraycompare(Index1, Index2: Integer): Integer;
begin
if MonTab[Index1].S1 > MonTab[Index2].S1 then
Result := -1
else if MonTab[Index1].S1 < MonTab[Index2].S1 then
Result := 1
else
Result := 0;
end;

procedure TForm1.ArrayExchange(Index1, Index2: Integer);
var
Temp: TMonType;
begin
Temp := MonTab[Index1];
MonTab[Index1]:= MonTab[Index2];
MonTab[Index2] := Temp;
end;

procedure TForm1.Button1click(Sender: TObject);
begin
with TQuickSort.Create(Arraycompare, ArrayExchange) do
SortAndFree(Low(MonTab), High(MonTab));
end;

Tu ne vas pas me dire que tu n'arrivais pas à faire ça en t'inspirant de mon exemple, non ?
Le cahier des charges est rempli: je trie selon S1 (ordre décroissant) et cela affecte l'ordre de S2
Messages postés
1023
Date d'inscription
dimanche 1 août 2004
Statut
Membre
Dernière intervention
17 août 2008

T'embette pas avec ça, je te donne la solution toute faite !
Messages postés
4716
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
27 mars 2018
11
désolé, mais j'ai reçu ta réponse après..
bien lu tout le code..
Mais je ne trouve pas SortAndFree dans ta publication à propos de l'algo de tri..

cantador
Messages postés
1023
Date d'inscription
dimanche 1 août 2004
Statut
Membre
Dernière intervention
17 août 2008

Oui, je me suis rendu compte après que nos messages se sont croisés.
Si, la procédure SortAndFree existe bel et bien.
Dans l'unité Sorts.pas, tu as la classe TSortAlgorithm qui possède cette méthode.
Et comme TQuickSort descend de TSortAlgorithm, il l'a aussi.

Si tu utilise mon code, cela fonctionne impec.
Messages postés
4716
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
27 mars 2018
11
Je ne trouve pas Sorts.pas mais Usorts.pas qui n'a pas SortAndFree mais Sort et SortAnyThing..
Je me demande si on évoque le même source..
et j'ai un souci de compil sur le OnClick du bouton..
sniff..
Bon je vais me coucher..

cantador
Messages postés
4716
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
27 mars 2018
11
Aurais-tu la possibilité de faire une petite modif de ton prog d'origine
afin de traiter ce cas particulier..
ça devrait en intéresser d'autres..


euh.. pas simple l'algo..

d'ailleurs DelphiProg avait écrit "Chapeau bas".

cantador
Messages postés
1023
Date d'inscription
dimanche 1 août 2004
Statut
Membre
Dernière intervention
17 août 2008

Ahhh non !
On ne parle pas de la même source !
J'ai fait une MAJ hier, maintenant l'unité s'appelle Sorts et la classe possède une méthode Sort and Free.

Re-télécharge la source, tu n'as pas la bonne version.
Si tu veux, je mettrai un exemple (tout à l'heure) pour ton cas mais sans toucher Sorts.pas !! D'ailleurs c'est facilement faisable mais je comprends qu'utiliser la source que quelqu'un d'autres est plus délicat que qu'une source de soi-même
Messages postés
4716
Date d'inscription
dimanche 26 février 2006
Statut
Modérateur
Dernière intervention
27 mars 2018
11
Ouf j'aime mieux ça bon ben finalement je vais prendre un café
eh oui Florenth, il y a tellement de bonnes publications sur DelphiFr que je ne sais plus où  donner de l'énergie..éplucher soigneusement et tout comprendre l'ensemble des sources est un travail de titan..
bon je reconnais néanmoins avoir peu été un peu fainéant sur ce coup..


REPONSE ACCEPTEE (zut, j'ai pas cliqué sur le bouton)
merci pour ta patience

cantador