Question pour un champion de mathsRésolu

Question

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

cs_Loda · Answer

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,

cs_cantador · Answer

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

cs_cantador · Answer

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

Emandhal · Answer

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...

cs_Loda · Answer

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,

cs_cantador · Answer

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

florenth · Answer

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

florenth · Answer

T'embette pas avec ça, je te donne la solution toute faite !

cs_cantador · Answer

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

florenth · Answer

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.

cs_cantador · Answer

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

cs_cantador · Answer

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

florenth · Answer

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

cs_cantador · Answer

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

Question pour un champion de maths

14 réponses

Votre réponse

Discussions similaires