tri d'un tableau

**benois123** · 07/12/2013, 22h59

Bonsoir,
j'ai un tableau deux dimensionnelle qui contient les éléments suivants

Code :

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

tel que L= ligne et C=colonne
je veux faire le tri de tel façon qu'il soit comme ceci

Code :

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

une idée svp
je sais pas par ou commencer

**Obsidian** · 07/12/2013, 23h18

Regarde qsort().

**benois123** · 08/12/2013, 10h38

j'ai pas bien compris . est ce que tu peux mieux m'expliquer ?
ou peut être une autre idée

Invité · 08/12/2013, 12h06

Bonjour,

En un peu plus détaillé : Du bon usage de qsort()

**benois123** · 08/12/2013, 12h13

Merci pour vos réponse
j'ai essayé de programmer l'idée mais il n'a pas marché voici

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
for(i=0;i<n;i++)
{
   for(j=i+1; j<n;j++)
    { /*on regarde les colonnes*/
      if(T[i].numcol==T[j].numcol)
       { /*on regarde les lignes*/
         if(T[j].numligne<T[j].numligne)
           /*permuter*/
       } 
     }
}

je sais pas comment fixer le problème

**Sve@r** · 08/12/2013, 12h53

Salut

Envoyé par benois123

ou peut être une autre idée

Oui bien évidemment. C'est tout à fait habituel, quand on a un outil qui fonctionne, d'en chercher un autre !!!

Envoyé par benois123

j'ai pas bien compris . est ce que tu peux mieux m'expliquer ?

qsort() est une fonction universelle permettant de trier tout tableau quel que soit son contenu. Elle compare les éléments et les permute quand ils ne sont pas à leur place. Quand elle a fini, tout le tableau est trié selon le voeu de l'utilsateur.
A partir de là, si tu réfléchis un minimum, tu te dis qu'elle doit quand-même avoir besoin d'un certain nombre d'éléments pour pouvoir bosser. En effet, elle a besoin

du tableau lui-même bien évidemment
de son nombre d'éléments afin qu'elle sache où s'arrêter
de la taille d'un élément afin de pouvoir les permuter
et d'une fonction lui permettant de comparer 2 éléments puisqu'elle ne sait pas ce qu'elle manipule. Et ça, c'est à l'utilisateur de la lui fournir puisque lui il sait ce qu'il veut trier. Il doit alors de son coté préparer une fonction permettant de comparer 2 éléments de son tableau et qui renverra -1, 0 ou 1 selon que l'élément 1 sera plus petit, égal ou plus grand que l'élément 2. Ensuite il lui suffit de passer l'adresse de cette fonction à qsort() qui pourra donc l'utiliser

Donc on appelle simplement qsort() en lui passant ces 4 trucs. Une fois qu'elle a fini de bosser, le tableau est trié. Je ne vois pas pourquoi il faudrait une autre idée...

Bon, à titre d'exemple, voici une démo

Code c :

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
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <stdlib.h>
 
void affiche(char *txt, int *tab[2])
{
	int i;
	for (i=0; i < 5; i++)
		printf("%s: ligne %d: %d - %d\n", txt, i, tab[i][0], tab[i][1]);
	fputc('\n', stdout);
}
 
int cmp(const void *t1, const void *t2)
{
	int i;
	for (i=1; i >= 0; i--)
	{
		if ((*(int **)t1)[i] < (*(int **)t2)[i])
			return -1;
		if ((*(int **)t1)[i] > (*(int **)t2)[i])
			return 1;
	}
	return 0;
}
 
int main()
{
	int tab[][2]={
		{5, 2},
		{4, 2},
		{8, 3},
		{10, 3},
		{9, 2},
	};
 
	// Un tableau [][] étant invariant, il faut le recopier dans un tableau de pointeurs
	int *tri[5];
	int i;
	for (i=0; i < 5; i++)
		tri[i]=tab[i];
 
	// Action
	affiche("avant tri", tri);
	qsort(tri, 5, sizeof(int*), cmp);
	affiche("après tri", tri);
}

Et le résultat

avant tri: ligne 0: 5 - 2
avant tri: ligne 1: 4 - 2
avant tri: ligne 2: 8 - 3
avant tri: ligne 3: 10 - 3
avant tri: ligne 4: 9 - 2

après tri: ligne 0: 4 - 2
après tri: ligne 1: 5 - 2
après tri: ligne 2: 9 - 2
après tri: ligne 3: 8 - 3
après tri: ligne 4: 10 - 3

Envoyé par benois123

j'ai un tableau deux dimensionnelle...

...voici

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
for(i=0;i<n;i++)
{
   for(j=i+1; j<n;j++)
    { /*on regarde les colonnes*/
      if(T[i].numcol==T[j].numcol)
       { /*on regarde les lignes*/
         if(T[j].numligne<T[j].numligne)
           /*permuter*/
       } 
     }
}

je sais pas comment fixer le problème

Commence déjà par nous donner les bons éléments. Un tableau bidimensionnel c'est un tableau[x][y] (comme un jeu d'échecs). On parlera d'ailleurs de tableau bi-dimensionnel (au masculin) ou à deux dimensions mais certainement pas de tableau "deux dimensionnelle".

Et ton code, lui, montre un tableau unidimensionnel (une liste) de structures. Ce n'est pas du tout la même chose !!!

Et je suis sûr que t'es même pas allé regarder la page donnée par Winjerome car le paragraphe XXXVIII-B-3. correspond exactement à ce que tu veux faire (tri d'un tableau de structures). C'est quand-même navrant quoi !!!

**benois123** · 08/12/2013, 23h31

Merci Sve@r pour votre idée ça marche bien mais j'ai un autre problème
j'ai mes données comme ça , en modifiant le programme que vous avez posté

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
 
avant tri: ligne 0: 5 - 2 - 2
avant tri: ligne 1: 4 - 2 - 2
avant tri: ligne 2: 8 - 3 - 2
avant tri: ligne 3: 10 - 3 - 2
avant tri: ligne 4: 9 - 2 - 2
avant tri: ligne 5: 9 - 3 - 4
avant tri: ligne 6: 5 - 3 - 4
avant tri: ligne 7: 4 - 3 - 4
avant tri: ligne 8: 7 - 4 - 18
avant tri: ligne 9: 8 - 4 - 18
avant tri: ligne 10: 9 - 4 - 18
avant tri: ligne 11: 10 - 4 - 18
avant tri: ligne 12: 5 - 4 - 18
avant tri: ligne 13: 8 - 5 - 48
avant tri: ligne 14: 9 - 5 - 48
avant tri: ligne 15: 10 - 5 - 48
avant tri: ligne 16: 7 - 5 - 48
avant tri: ligne 17: 10 - 6 - 62
avant tri: ligne 18: 8 - 6 - 62
avant tri: ligne 19: 8 - 7 - 68
avant tri: ligne 20: 9 - 7 - 68
avant tri: ligne 21: 10 - 7 - 68
avant tri: ligne 22: 9 - 8 - 106

alors je veux trier par exemple seule les éléments qui ont la même valeur de troisième colonne ,
premièrement je veux trier les éléments qui ont une valeur 2 puis trier les éléments qui ont la valeur de troisième colonne 4 etc ce qui donne le tri suivant

Code :

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

or moi le code m'affiche comme ça

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
 
après tri: ligne 0: 4 - 2 - 2
après tri: ligne 1: 5 - 2 - 2
après tri: ligne 2: 9 - 2 - 2
après tri: ligne 3: 4 - 3 - 4
après tri: ligne 4: 5 - 3 - 4
après tri: ligne 5: 8 - 3 - 2
après tri: ligne 6: 9 - 3 - 4
après tri: ligne 7: 10 - 3 - 2
après tri: ligne 8: 5 - 4 - 18
après tri: ligne 9: 7 - 4 - 18
après tri: ligne 10: 8 - 4 - 18
après tri: ligne 11: 9 - 4 - 18
après tri: ligne 12: 10 - 4 - 18
après tri: ligne 13: 7 - 5 - 48
après tri: ligne 14: 8 - 5 - 48
après tri: ligne 15: 9 - 5 - 48
après tri: ligne 16: 10 - 5 - 48
après tri: ligne 17: 8 - 6 - 62
après tri: ligne 18: 10 - 6 - 62
après tri: ligne 19: 8 - 7 - 68
après tri: ligne 20: 9 - 7 - 68
après tri: ligne 21: 10 - 7 - 68
après tri: ligne 22: 9 - 8 - 106

Aidez moi svp
quelle sont les modifications que je fais pour qu'il m'affiche des résultats correctement ??

**Sve@r** · 08/12/2013, 23h52

Envoyé par benois123

alors je veux trier par exemple seule les éléments qui ont la même valeur de troisième colonne ,

Donc maintenant il y a une troisième colonne. On dirait Perceval quand il raconte une de ses quêtes (kaamelott)...

Envoyé par benois123

premièrement je veux trier les éléments qui ont une valeur 2 puis trier les éléments qui ont la valeur de troisième colonne 4 etc
ce qui donne le tri suivant

Code :

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

Oui donc en fait au lieu d'avoir un tri sur la 2° colonne puis sur la 1ère, tu veux un tri sur la 3° puis la 2° puis la 1ère.

Envoyé par benois123

or moi le code m'affiche comme ça ...

Ouais, t'as raison de donner le résultat mais pas le code, cela aurait été trop simple sinon...

Envoyé par benois123

quelle sont les modifications que je fais pour qu'il m'affiche des résultats correctement ??

Si t'avais à peine réfléchi à "comment s'exprime ton besoin et comment je l'ai traduit dans mon code", t'aurais trouvé tout seul.

Code c :

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <stdio.h>
#include <stdlib.h>
 
void affiche(char *txt, int *tab[2], size_t nb)
{
	int i;
	for (i=0; i < nb; i++)
		printf("%s: ligne %d: %d - %d - %d\n", txt, i, tab[i][0], tab[i][1], tab[i][2]);
	fputc('\n', stdout);
}

int cmp(const void *t1, const void *t2)
{
	int i;
	for (i=2; i >= 0; i--)
	{
		if ((*(int **)t1)[i] < (*(int **)t2)[i])
			return -1;
		if ((*(int **)t1)[i] > (*(int **)t2)[i])
			return 1;
	}
	return 0;
}

int main()
{
	int tab[][3]={
		{5, 2, 2},
		{4, 2, 2},
		{8, 3, 2},
		{10, 3, 2},
		{9, 2, 2},
		{9, 3, 4},
		{5, 3, 4},
		{4, 3, 4},
		{7, 4, 18},
		{8, 4, 18},
		{9, 4, 18},
		{10, 4, 18},
		{5, 4, 18},
		{8, 5, 48},
		{9, 5, 48},
	};

	// Un tableau [][] étant invariant, il faut le recopier dans un tableau de pointeurs
	int *tri[15];
	int i;
	for (i=0; i < 15; i++)
		tri[i]=tab[i];

	affiche("avant tri", tri, 15);
	qsort(tri, 15, sizeof(int*), cmp);
	affiche("après tri", tri, 15);
}

Les différences avec le précédent ? Tout simplement la fonction de comparaison qui travaille maintenant sur 3 colonnes alors qu'avant elle ne travaillait que sur 2 (en rouge dans mon source)
J'ai aussi modifié la fonction d'affichage en remplaçant le nb d'éléments à afficher (auparavant un nombre en dur) par une variable mais cela n'a pas d'effet sur le tri proprement dit.

Et le résultat

avant tri: ligne 0: 5 - 2 - 2
avant tri: ligne 1: 4 - 2 - 2
avant tri: ligne 2: 8 - 3 - 2
avant tri: ligne 3: 10 - 3 - 2
avant tri: ligne 4: 9 - 2 - 2
avant tri: ligne 5: 9 - 3 - 4
avant tri: ligne 6: 5 - 3 - 4
avant tri: ligne 7: 4 - 3 - 4
avant tri: ligne 8: 7 - 4 - 18
avant tri: ligne 9: 8 - 4 - 18
avant tri: ligne 10: 9 - 4 - 18
avant tri: ligne 11: 10 - 4 - 18
avant tri: ligne 12: 5 - 4 - 18
avant tri: ligne 13: 8 - 5 - 48
avant tri: ligne 14: 9 - 5 - 48

après tri: ligne 0: 4 - 2 - 2
après tri: ligne 1: 5 - 2 - 2
après tri: ligne 2: 9 - 2 - 2
après tri: ligne 3: 8 - 3 - 2
après tri: ligne 4: 10 - 3 - 2
après tri: ligne 5: 4 - 3 - 4
après tri: ligne 6: 5 - 3 - 4
après tri: ligne 7: 9 - 3 - 4
après tri: ligne 8: 5 - 4 - 18
après tri: ligne 9: 7 - 4 - 18
après tri: ligne 10: 8 - 4 - 18
après tri: ligne 11: 9 - 4 - 18
après tri: ligne 12: 10 - 4 - 18
après tri: ligne 13: 8 - 5 - 48
après tri: ligne 14: 9 - 5 - 48

**Médinoc** · 09/12/2013, 09h00

Ce n'est pas très lisible, ça

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
int cmp(const void *t1, const void *t2)
{
	int i;
	for (i=1; i >= 0; i--)
	{
		if ((*(int **)t1)[i] < (*(int **)t2)[i])
			return -1;
		if ((*(int **)t1)[i] > (*(int **)t2)[i])
			return 1;
	}
	return 0;
}

Tu pourrais au moins centraliser les casts:

Code C :

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
/*Si qsort() est appelé sur un tableau de pointeur sur tableau,
  cmp() est appelé sur deux pointeurs de pointeur sur tableau*/
int cmp(const void *v1, const void *v2)
{
	int const * const * pt1 = v1;
	int const * const * pt2 = v2;
	int const * t1 = *pt1;
	int const * t2 = *pt2;
	/*On compare chaque valeur des tableaux pointés, en partant de la droite*/
	int i;
	for (i=NOMBRE_COLONNES-1; i >= 0; i--)
	{
		if (t1[i] < t2[i])
			return -1;
		if (t1[i] > t2[i])
			return 1;
	}
	return 0;
}

**Sve@r** · 09/12/2013, 15h39

Envoyé par Médinoc

Ce n'est pas très lisible, ça...

Oui ben codé un peu à l'arrache. Déjà que le PO ne s'était pas embêté à poser un cahier des charges bien propre, je n'allais pas m'embêter en retour à clarifier une fonction peut-être au final inutile. Et le but était surtout plus d'expliquer le principe de qsort() que de détailler à fond la fonction de comparaison qui pouvait faire ensuite l'objet d'un nouveau post si le PO était intéressé...

Envoyé par Médinoc

Tu pourrais au moins centraliser les casts:

Code C :

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
/*Si qsort() est appelé sur un tableau de pointeur sur tableau,
  cmp() est appelé sur deux pointeurs de pointeur sur tableau*/
int cmp(const void *v1, const void *v2)
{
	int const * const * pt1 = v1;
	int const * const * pt2 = v2;
	int const * t1 = *pt1;
	int const * t2 = *pt2;
	/*On compare chaque valeur des tableaux pointés, en partant de la droite*/
	int i;
	for (i=NOMBRE_COLONNES-1; i >= 0; i--)
	{
		if (t1[i] < t2[i])
			return -1;
		if (t1[i] > t2[i])
			return 1;
	}
	return 0;
}

Tu pourrais au-moins éviter les variables inutiles...

Code c :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int cmp(const void* v1, const void* v2)
{
	int i;
	int const* t1=*(int const* const*)v1;
	int const* t2=*(int const* const*)v2;
	for (i=2; i >= 0; i--)
	{
		if (t1[i] < t2[i])
			return -1;
		if (t1[i] > t2[i])
			return 1;
	}
	return 0;
}

tri d'un tableau

C

Discussions similaires

Partager

Partager