tri par orde croissant

Version imprimable

26/06/2015, 18h15
Thierry_28

tri par orde croissant
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:

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:

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:

1 2 3 [2 et 0] = 8 [2 et 1] = 11 [2 et 3] = 7
Le tableau trié sera :
Code:

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

'Soir

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

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); });

Bonjour,

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

Code:

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:

Merci et bonne journée.

01/07/2015, 12h33
Ehonn

Troll : il manque l'appel à std::sort.
01/07/2015, 12h50
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.

Citation:

Envoyé par Ehonn

Troll : il manque l'appel à std::sort.
01/07/2015, 13h03
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:

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

Citation:
Envoyé par 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:

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:

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:

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:

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.

Voici un code que tu pourras adapter.

Code:

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';
  }
}