Discussion :

[Thierry_28]

Bonjour à tous,

Je sollicite votre aide pour me coder cet exercice :

Je dispose d'une matrice de distance (diagonale) entre des zones géographiques : matrice[i][j]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
0	5	8	14
5	0	11	20
8	11	0	7
14	20	7	0

Dans un premier temps, je tire aléatoirement une zone parmi les 4. Supposant qu'on tire la zone numéro 2, on la stocke dans la première case du tableau "trisecteur" :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

trisecteur[0] = 2

Je souhaiterai faire un tri par distance croissante par rapport a trisecteur[0].
Si on prend l'exemple : on va comparer la distance entre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
[2 et 0] = 8
[2 et 1] = 11
[2 et 3] = 7

Le tableau trié sera :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
trisecteur[0] = 2
trisecteur[1] = 3
trisecteur[2] = 0
trisecteur[3] = 1

Merci.

[jo_link_noir]

'Soir

Tu peux utiliser std::sort avec un foncteur ou une lambda de comparaison:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
std::sort(begin(trisecteur), end(trisecteur), [&, x=trisecteur[0]](unsigned i1, unsigned i2) {
  return abs(matrice[2][i1] - x) < std::abs(matrice[2][i1] - x); 
});

[Thierry_28]

Bonjour,

J'ai fait un essai mais ça marche pas. Pourriez-vous regarder ce qui va pas ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// tri par insertion
	int memoire; // memoire:valeur en cours de traitement
	int compteur; // indique la partie du tableau a traiter
	bool marqueur; // faut-il continuer les comparaisons?
	int trisecteur[NbrSecteurs];
 
	trisecteur[0]=rand()%NbrSecteurs; // tirer aleatoirement un secteur
 
	for(i=1; i<NbrSecteurs; i++){
		for(j=1; j<NbrSecteurs; j++){
			memoire = matrice_secteurs[trisecteur[0]][j];
			compteur = i-1;
			do
			{
				marqueur = false;
				// comparaisons et décalages vers la droite si nécessaire
				if(matrice_secteurs[trisecteur[0]][compteur] > memoire)
					{
						cerr << " i " << i << " M " << matrice_secteurs[trisecteur[0]][compteur] << " memoire " << memoire << endl;
						trisecteur[compteur+1] =  compteur;
						compteur--;
						marqueur = true;
						}
						if(compteur < 0) // on évite de dépasser les limites
							marqueur = false;
						}
						while(marqueur);
		}
	}
	trisecteur[compteur+1] = compteur;
	// Affichage pour verification
 
	for(i=0; i<NbrSecteurs; i++){
		cerr << " i " << i << " =  " << trisecteur[i] << endl;
	}

Le résultat du tableau est incorrect :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
i 0 =  2
i 1 =  0
i 2 =  1
i 3 =  0
i 4 =  3
i 5 =  4
i 6 =  5
i 7 =  6
i 8 =  7

Merci et bonne journée.

[Ehonn]

Troll : il manque l'appel à std::sort.

[Thierry_28]

Est ce que tu peux m'expliquer plus stp ? à ma connaissance, le std::sort est utilisé pour les vecteurs ce qui n'est pas le cas pour moi.

Troll : il manque l'appel à std::sort.

[Ehonn]

Avec plaisir (tu aurais du détailler ton souci avec std::sort dans le message d'avant)

std::sort est générique, il fonctionne avec des itérateurs et pas uniquement ceux d'std::vector. Il se trouve que les adresses (pointeurs) se comportent comme des random access iterators (c'est le type d'itérateur requis pour cette fonction).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
#include <algorithm>
// ...
std::sort(trisecteur, trisecteur + NbrSecteurs);

Si tu as le choix, tu devrais utiliser std::vector ou std::array plutôt que les tableaux "à la C".

[Thierry_28]

Avec plaisir (tu aurais du détailler ton souci avec std::sort dans le message d'avant)

std::sort est générique, il fonctionne avec des itérateurs et pas uniquement ceux d'std::vector. Il se trouve que les adresses (pointeurs) se comportent comme des random access iterators (c'est le type d'itérateur requis pour cette fonction).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
#include <algorithm>
// ...
std::sort(trisecteur, trisecteur + NbrSecteurs);

Si tu as le choix, tu devrais utiliser std::vector ou std::array plutôt que les tableaux "à la C".

Merci mais j'ai utilisé les tableaux car je me sens plus alaise. Cependant, j'ai réussi à trier les distances par ordre croissant mais ce que je souhaiterai c'est de trier les numéros des secteurs dans le tableau trisecteur.

Merci de me modifier ce code pour que j'obtiens le résultat souhaité.
Voici le code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
 
int trisecteur[NbrSecteurs];
	trisecteur[0]=rand()%NbrSecteurs; // tirer aleatoirement un secteur
	cerr << " secteur tire : " << trisecteur[0] << endl;
 
	cerr << " ****** list of distance ******* " << endl;
	for(i=0; i<NbrSecteurs; i++)
	{
		cerr << " i " << i << " = " <<  matrice_secteurs[trisecteur[0]][i] << endl;
	}
 
int memoire_1;
	for(i=1; i<NbrSecteurs; i++)
	{
		memoire_1 = matrice_secteurs[trisecteur[0]][i];
		j = i;
		while( j >0 && matrice_secteurs[trisecteur[0]][j-1] >  memoire_1)
		{
			matrice_secteurs[trisecteur[0]][j] = matrice_secteurs[trisecteur[0]][j-1];
            j = j - 1;
		}
		matrice_secteurs[trisecteur[0]][j] = memoire_1;
	}
 
	cerr << " ****** Affichage des distances triees ******* " << endl;
	for(i=0; i<NbrSecteurs; i++)
	{
		cerr << " i " << i << " = " <<  matrice_secteurs[trisecteur[0]][i] << endl;
	}

Le résultat de ce code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 secteur tire : 8
 ****** list of distance *******
 i 0 = 47
 i 1 = 88
 i 2 = 86
 i 3 = 26
 i 4 = 39
 i 5 = 99
 i 6 = 56
 i 7 = 71
 i 8 = 0
 ****** Affichage des distances triees *******
 i 0 = 0
 i 1 = 26
 i 2 = 39
 i 3 = 47
 i 4 = 56
 i 5 = 71
 i 6 = 86
 i 7 = 88
 i 8 = 99

Ce que je cherche est d'avoir le tableau trié sous cette forme (numéro des secteurs) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
 i 0 = 8
 i 1 = 3
 i 2 = 4
 i 3 = 0
 i 4 = 6
 i 5 = 7
 i 6 = 2
 i 7 = 1
 i 8 = 5

merci d'avance.

[jo_link_noir]

Voici un code que tu pourras adapter.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
 
int main() {
  int tab[] = {3,6,8,3,2,0};    
  unsigned indexes[] = {0,1,2,3,4,5}; // std::iota
 
  using std::begin;
  using std::end;
  std::sort(begin(indexes), end(indexes), [&](unsigned x, unsigned y) {
    return tab[x] < tab[y];
  });
 
  for (auto i : indexes) {
    std::cout << '[' << i << "] " << tab[i] << '\n';
  }
}