Posez votre question Signaler

[c++] tri de tableau

robert - Dernière réponse le 18 déc. 2006 à 00:42
Bonsoir,
j'aimerais faire un tri d'un tableau contenant des types point composé de x (ordonné) et de t (le temps), et j'aimerais trier le tableau efficacement
en ordre croissant en fonction de t plus précisément trier le tableau pointé par pv. voici mon code dont je vous épargne son intégralité
Merci d'avance
class Point {
public:
double x, t;
Point( double x = 0.0, double t= 1) : x(x), t(t) {}
friend Point milieu( const Point & p, const Point & q);
friend Point gauss2D( const Point & moy = Point(), double sig2 = 1.0);
};
struct Brown2D {
Point q;
Brown2D *s;
};
Point milieu( const Point & p, const Point & q) {
double x = (p.x + q.x)/2.0;
double t = (p.t + q.t)/2.0;
return Point(x,t);
}
int main() {
srand( time(0));
Brown2D B1 = { Point(gauss2D()), 0 },//considérer B1 et B0
B0 = { Point(0,0), &B1 };//comme despoints
Brown2D *pg, *pm, *pd; // pointeurs gauche, milieu, droite
int N=3;
Point *pv=new Point [N];
pv[0]=Point(0,0);
pv[N-1]=B1.q;
for ( int n = 1 ; n < N ; n ++ ) {
for ( pg = &B0 ; pd = pg->s ; pg = pd ) {
pm = new Brown2D;
pm->q = gauss2D( milieu( pg->q, pd->q),
abs(pd->q.t - pg->q.t)/4);
pv[n]=Point(pm->q.x,pm->q.t);//ici pv prend tous les points(x,t) mais dans le desordre
pm->s = pg->s;
pg->s = pm;
pm->q.plot();
}
}
}
Lire la suite 

[c++] tri de tableau »

6 réponses
Réponse
+1
moins plus
je pense qu'il y a plus simple

moi j'ai fait un tri d'un tableau a une dimension en une dizaine de lignes

en gros je prenais une case (la 1ere pour commencer) et je la comprai a celle d'apres et je permutait les deuc cases si l'une devait eytre avant ou apres l'autre (selon le tri que tu veu faire) une fois que j'avai comprarer la premier case avec celle d'apres je prenai la deuxieme case que je comparais avec celle d'apres et ainsi de suite jusqu'a l'avant dernier case ou la le tableau doit etre trie

j'ai creer une methode permuter
et sinon j'ai utiliser 2 boucle pour et un si (pour verifier si y'a besoin de permuter)

voila si ca peut t'aider...
robert - 17 déc. 2006 à 17:09
ok je vais essayer merci a tous pour vos conseils
bien cordialement
mamiemando - 18 déc. 2006 à 00:42
Lapinkiller : Moi je donne la méthode générique et qui marche en O(log(n)), après chacun fait ce qu'il veut... Et la définition de l'opérateur < ou du foncteur tient en moins de dix lignes.
inline bool operator<(const Point & p1,const Point & p2){
  return p1.t < p2.t || (p1.t == p2.t && p1.x < p2.x);
}

Les foncteurs sont intéressant si un opérateur < a déjà été défini et qu'on souhaite utiliser une autre relation d'ordre pour trier le set. A noter que si les doublons sont autorisés dans la liste, il faut utiliser un multiset.

Bonne chance
Ajouter un commentaire
Réponse
+0
moins plus
en fait tu veu trier ton tableau du plus petit au plus grand c'est ca ? avec t comme reference de triage...
robert - 16 déc. 2006 à 23:26
oue voila c'est tous a fait sa tu a une proposition....merci d'avance.
Ajouter un commentaire
Réponse
+0
moins plus
Il faut redéfinir l'opérateur < sur ta classe point ou définir un foncteur.
Exemple :
#include <set>
#include <iostream>

class Point{
  public:
  double x,t;
  Point(const double & x0,const double & t0):x(x0),t(t0){}
  //...
};

struct cmp_time{
  inline bool operator()(const Point & p1,const Point & p2){
    return p1.t < p2.t || (p1.t == p2.t && p1.x < p2.x);
  }
}

int main(){
  // Construire l'ensemble de points ordonnés sur le temps
  Point p1(3,5),p2(7,2),p3(6,9);
  std::set<Point,cmp_time> ens_pts;
  ens_pts.insert(p1);
  ens_pts.insert(p2);
  ens_pts.insert(p3);

  // Afficher l'ensemble de poitns
  std::set<Point,cmp_time>::const_iterator
    sit(ens_pts.begin()),send(ens_pts.end())
  for(;sit!=send;++sit){
    const Point & pcur = *sit;
    std::cout << pcur.x << '\t' << pcur.t << std::endl;
  }
  return 0;
}

Par defaut si le comparateur du set n'est pas spécifié, on utilise le foncteur par défaut qui repose sur le relation < (ici celle de la classe Point). Dans ton cas il faudrait définir l'opérateur < pour pouvoir écrire directement :
std::set<Point>

Exemple :
...
inline bool operator<(const Point & p1,const Point & p2){
  return p1.t < p2.t || (p1.t == p2.t && p1.x < p2.x);
}

int main(){
  std::set<Poiont> ens_points2;
  //...
  return 0;
}


Bonne chance
Ajouter un commentaire
Ce document intitulé « [c++] tri de tableau » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.
Dossier à la une
5 extensions si vous voulez revenir à l'ancien Facebook