COMMENT TRIER UNE MATRICE
Arnaud16022
Messages postés
1329
Date d'inscription
vendredi 15 août 2003
Statut
Membre
Dernière intervention
16 juin 2010
-
20 mars 2007 à 18:13
gueroihi - 19 févr. 2017 à 15:58
gueroihi - 19 févr. 2017 à 15:58
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/41906-comment-trier-une-matrice
https://codes-sources.commentcamarche.net/source/41906-comment-trier-une-matrice
19 févr. 2017 à 15:58
réalisé par moi: gueroihi mohamed.
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
main()
{ int M[3][3]={{8,4,6},{7,5,1},{4,9,2}};
int n,m,i,j,k,l,imin,jmin,jj,aux;
n=3;
m=3;
//Affichage avant le tri
printf("Matrice initiale:\n");
for(i=0;i<m;i++)
{ for(j=0;j<n;j++)
printf("%d\t",M[i][j]);
printf("\n");
}
//Le tri (tri par selection)
for (i=0;i<n;i++)
for (j=0;j<m;j++)
{ imin=i;
jmin=j;
for (k=i;k<n;k++)
{ if (k==i) jj=j+1; else jj=0;
for (l=jj;l<m;l++)
if (M[k][l]<M[imin][jmin])
{
imin=k; jmin=l;
}
}
//permutation
aux=M[i][j];
M[i][j]=M[imin][jmin] ;
M[imin][jmin]=aux;
}
//Affichage apres le tri
printf("\n\nmatrice triee:\n");
for(i=0;i<m;i++)
{ for(j=0;j<n;j++)
printf("%d\t",M[i][j]);
printf("\n");
}
getch();
}
21 déc. 2009 à 16:01
import java.util.*;
public class tri {
//par le leader
//Tarik
public static void main(String[] args) throws IOException{
BufferedReader c=new BufferedReader(new InputStreamReader (System.in) ) ; // TODO, add your application code
System.out.println("Hello World!");
int tableau[][]=new int [4][4];
for(int i=0;i<4;i++)
{ for(int ii=0;ii<4;ii++)
{
int j=(int)(Math.random() * (100-0)) + 0;
tableau[i][ii]=j;
System.out.print (" "+tableau[i][ii]);
}System.out.println ();}
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
for(int ii=0;ii<4;ii++)
{
for(int jj=0;jj<4;jj++)
{
if(tableau[i][j]<tableau[ii][jj])
{
int aux = tableau[i][j];
tableau[i][j]= tableau[ii][jj];
tableau[ii][jj] = aux;
}}}}}
System.out.println ();
for(int i=0;i<4;i++)
{ for(int ii=0;ii<4;ii++)
{
System.out.print (" "+tableau[i][ii]);}System.out.println ();}
System.out.println ("par tarik contactez-moi sur leader_tariman@hotmail.fr" );
}
}
23 mars 2007 à 21:33
Grâce à vous j'ai deviné à quel point je suis stupide !
Je comprends à présent votre proposition et je ne vais pas tarder à l'implémenter.
Merci beaucoup.
23 mars 2007 à 19:17
23 mars 2007 à 14:26
Le problème est toujours là : vous vous êtes servi d'un tableau intermédiaire pour trier ma matrice !!! C'est justement ce que je veux éviter !!!
int * matrice;
int * tableau;
tableau = (int*) malloc(x*y*4);
matrice = tableau;
// remplissage de la matrice
// bubble sort du tableau
// La matrice est triée.....
Merci quand même !!
Byyyyyyyyyyyyyyyyyyyyyyyyyye!
22 mars 2007 à 17:57
pour ton pb c'est très facile lol
int * matrice;
int * tableau;
tableau = (int*) malloc(x*y*4);
matrice = tableau;
// remplissage de la matrice
// bubble sort du tableau
// La matrice est triée.....
note que le C++ c'est le bien: dans ta classe CMatrice tu pourrais défininir l'operator(x,y) comme setter , évitant d'avoir à écrire matrice[y*largeur+x]. Car effectivement tu ne pourras pas accéder à tes cases comme ça [x][y]; mais c'est de toute façon très mauvais car c'est une notation utilisable uniquement pour des objets situés sur la pile. Global, c'est mal .
22 mars 2007 à 17:32
Pardon, vous avez tout à fait raison.
Thank you very much indeed !
22 mars 2007 à 17:27
Je vérifie (dubito ergo cogito...) et lis :
short : 2 Bytes
int : 4 Bytes d'où sizeof(int) = 4
Ceci dit tu peux toujours tester si tu ne me crois pas et sur la plupart des architectures... sizeof(int)=4 !
Bon courage... :/
22 mars 2007 à 17:16
Monsieur Kirua :
Vous nous avez bien expliqué que la structure de données 'Matrice' est purement
conceptuelle et que le processeur la traite comme un tableau classique à une seule dimension.
Mais, en fait, il est manifeste que vous n'avez pas répondu à ma question : il serait infiniment
appréciable de nous communiquer votre code C implémentant le tri d'une matrice sans
dupliquer les données de ladite matrice dans un autre tableau intermédiaire. Je vous répète : je suis trop curieux
de savoir comment y procéder !? Depuis l'année passée c'est la seule idée qui me venait
à l'esprit (à savoir : avoir le recours -même conceptuel- à un tableau).
Faites-nous montrer votre alternative -le code C à l'appui. Et merci !
Monsieur Patemino :
sizeof(int) = 2 !
veuillez consulter www.cplusplus.com.\doc\tutorial\variables.html pour la vérification.
See you soon and GoooooooooooooodByyyyyyyyyyyye !!!
22 mars 2007 à 15:33
Je ne veux ni vous froisser, ni vous blesser, ni vous ni votre ego mais :
sizeof(int)=4
Juste en passant comme ça hein ^^
Sur ce, salutations !
Arnaud, Kirua iop!
22 mars 2007 à 12:00
22 mars 2007 à 11:52
Monsieur Arnaud, vous avez a eu la magnanimité de vous exprimer : je vous suis redevable de gratitude.
Désolé : je ne puis vous tutoyer car même si je suis plus âgé que vous, il me semble que votre cerveau dépasse aussi bien votre âge que le mien (comprendre : je salue votre sagesse et votre bonté).
De ma part, je vous ai bien compris, d'ailleurs j'ai bien noté :" En fait, c'est juste une manière pour aborder ma réponse." Et là il fallait appréhender "C'est juste une plaisanterie pour commencer !". Apparemment je me suis juste mal exprimé. Pardon.
J'ai bien cerné qu'il n'y a rien de méchant dans votre intervention surtout que, même si l'on est de cultures différentes (Je suis Kabyle ?Algérie-), je suis en mesure de comprendre autrui (vous qui êtes là bas) aisément d'autant plus que je lisais presque régulièrement les commentaires des sources qui m'apportent un plus, ici sur cppfrance, depuis plus de 2 ans.
Revenons à nos moutons !
Pour ce qui est de l'utilité du tri matriciel, et comme je vous ai déjà répondu, on se sert intensivement des matrices dans le monde mystérieux du "image processing" : on y trouve des opérations matricielles mystérieuses. Certes, je n'y ai pas encore glané ce qui ressemble à un tri, mais je pense qu'il se pourrait bien qu'il y ait un quelconque
'accueil' pour le tri des matrices. Ou alors que ledit tri servirait ailleurs : qu'il est vaste le monde de la recherche. Mais, je tiens à vous souligner, que moi-même je ne puis répondre à votre question : à quoi bon de trier une matrice ?! Une intervention dans ce sens de la part de cette kyrielle de développeur en C/C++ de la toile cppfrance serait certainement appréciée aussi bien pour vous que moi.
Je tiens à signaler le fait que ce code je l'ai implémenté au cours de l'année scolaire qui a précédé : ce fût une aide de ma part à un étudiant d'une autre filière que l'informatique qui n'arrivait pas à le solutionner.
Et puis lorsque vous dites qu'en vue de trier des donnée on puit se servir simplement des tableaux je suis désolé de vous dire que je ne suis point tout à fait d'accord avec vous : Primo, le compilateur du C traite lui-même les tableaux en tant que pointeurs (comprendre que le recours aux listes par exemple serait plus pertinent) ; secundo, en pratique, on a besoin d'effectuer autre chose sur les données, en plus du tri, et dans cet 'autre chose' les tableaux ne s'apprête point à honorer les tâches pour des raisons que tout le monde comprend bien.
Apparemment notre second gentil homme ?Monsieur Kirua- m'a mal compris, idem.
Il m'est plaisir de vous demander de l'excuse. Nonobstant, ce que j'aimerais, chers Messieurs, est que je me suis beaucoup plus attendu à une critique bien plus pertinente : alias j'ai eu recours à un tableau pour trier une matrice. Je trouve moi-même ça très incommode ; ainsi, pour une matrice de 1000 éléments j'aurais besoin d'un tableau d'un million (1000 000) de cases ce qui équivaut à plus de deux millions (2000 000) d'octets pour des données aussi simples que celle du type "int" ! Ajouté à cela la complexité du tri du tableau lui-même et tous ces transferts coûteux aussi bien en mémoire qu'en temps ! Ainsi, vous devinez à présent, que mon souhait fût de faire une suggestion dans ce sens : y'a-t-il un autre moyen pour trier notre chère matrice autrement que de 'solliciter' un tableau ? Et j'espère recevoir un écho à cette requête.
Je tiens à vous remercier infiniment Monsieur pour le fait de m'avoir informé que le processeur traite les matrices comme des tableaux ! (Que c'est intuitif, certes, mais j'aurais dû y penser !).
Cher Monsieur Arnaud ;
Vous m'avez écris : "Jamais, jamais dit ça". J'ai y beaucoup ri : comme si vous étiez dans un commissariat de police ! ?Que vous êtes honnête et sincère !-
Sachez que vous n'avez aucune raison d'avoir peur de moi : vous n'étiez point violent dans vos propos ; moi non plus. Toutefois, je pense que vous avez le don de l'intuition : vous avez raison d'avoir peur de moi et il y a un endroit où il serait très méchant de songer y me rencontrer : le ring. Oui, je suis un pratiquant régulier d'arts martiaux.
J'espère que vous ne m'avez pas mal compris là encore Monsieur Arnaud ! "Just Kidding" comme disent les Anglais (comprendre : je plaisante seulement ! ?Mais il est vrai : je pratique les arts martiaux-).
L'esprit et l'envie de la paix coule dans mes veines : Ici en Algérie, on a subi pendant plus d'une décennie la barbarie du terrorisme islamiste ce qui fait de moi ?ainsi que tous les Algériens- des gens assoiffés de la liberté et de la paix. Je répugne la violence dans les propos mais aussi dans l'acte et l'action. Je rejette toute forme de violence c'est ce n'est celle qui me sert d'auto défense. La paix est une bonne chose ; et les bonnes choses sont éternelles. Que ce qui est bon règnera. Que la compréhension entre les peuples soit la monnaie d'échange de l'homme qui se vante vouloir être l'homme d'aujourd'hui et l'homme du futur. Rêvons à une société de défis, de progrès, de science, de communication et de respect mutuel. Car ceci aussi relève des bonnes choses.
Il se puit bien que l'on me juge entrain d'exprimer des positions ne faisant pas partie de la programmation. Mais dites-moi : une science non humaine à qui bon ? J'ai le souhait, d'ailleurs, de trouver dans des FAQ comme celle-là un foyer de communication, de compréhension et de respect mutuelle entre les cultures aussi différentes soient-elles. Je suis alors, naïf, me diriez-vous. Mon esprit scientifique puit, peut être, vous donner raison ; il est illusoire d'espérer cette approbation de la part de mon esprit de l'homme d'aujourd'hui et de demain.
J'ai posté ce message ici, vous le voyez. De même, je l'ai envoyé personnellement à Monsieur Arnaud dans l'espoir qu'il le lit.
En tout cas, je n'ai exprimé que ce que je sais ; je sais que la paix est plus qu'un besoin pour l'humanité.
Je suis bavard, je le sais, alors je vous demande Pardon là encore !
21 mars 2007 à 22:54
Bonsoir :)
21 mars 2007 à 12:44
"Je serais heureux de recevoir vos critiques constructives."
Volontiers; il me semble que c'est ce que j'ai fait, mais apparement je me suis mal fait comprendre, désolé.
"BONJOUR MONSIEUR ARNAUD16022;"
Pas de caps lock, merci. Et on peut se tutoyer je pense ? Monsieur ^^ tu me rends vieux; nous avons tous les deux dans la vingtaine.
"J'AI L'IMPRESSION QUE VOUS AVEZ LU MON CODE LA RAGE AU C'UR !"
Absolument pas. Je dois même avouer que je suis très étonné de ta réaction. Je m'excuse sincèrement si j'ai pu paraître en colère ou autre. Je pose simplement la question : pour toi , qu'est-ce qu'une matrice triée ? ( Comprendre : mathématiquement, c'est quoi ? )
J'essayais juste de dire que le tri d'une matrice n'est pas quelque chose de ... hum, réaliste.
Prenons un cas concret.
J'ai besoin de trier des valeurs. Dans quoi les mets-je ? une matrice ? certainement pas, j'ai déjà un conteneur bien plus efficace pour cela, les tableaux. Je te rappelle que le tri s'effectue en O( n log(n) ) avec un tri rapide ou par fusion.
J'ai besoin d'effectuer un calcul mathématique. Là par contre c'est stupide de prendre un tableau, une matrice est en algèbre linéaire beaucoup plus adaptée. Je pense que jusque là nous sommes d'accord.
Mais la où je ne comprends vraiment pas ta démarche, c'est dans le fait de trier tes cases... à quoi bon ? vraiment ça me dépasse et j'aimerais réellement une explication.
Et soit dit en passant, quand A ? Mn(R), dim(X) = n et non n² ( X ? R^n ) ; mais je suppose que c'est une simple notation d'appeller ton int vecteur[100]; comme ça.
"COMME SI MON CODE EST LE PLUS IDIOT QUI N'EST JAMAIS DEPOSé sur la toile !"
Jamais, jamais dit ça . Je ne suis pas un petit noob de 13 ans qui veut se la péter et qui met des commentaires à la va vite.
"Votre 2ème intervention est intéressante : elle suggère une autre conception du tri matricielle."
Ce n'est pas exactement ce que je voulais dire, là aussi ... Toi tu parles de trier les éléments de ta matrice, moi je parlais de trier plusieurs matrices différentes.
Voilà :) Encore une fois, désolé si ce que j'ai écrit t'a paru trop violent.
Bonne journée, j'attends tes commentaires et réponses.
Arnaud
20 mars 2007 à 21:31
J'AI L'IMPRESSION QUE VOUS AVEZ LU MON CODE LA RAGE AU C'UR !
COMME SI MON CODE EST LE PLUS IDIOT QUI N'EST JAMAIS DEPOSé sur la toile !
En fait, c'est juste une manière pour aborder ma réponse.
En effet, moult fois j'ai lu des articles sur le traitement d'images : c'est un monde fascinant où les matrices ont un rôle primordiale. Tout ce fait à base d'opérations matricielles trop mystérieuses et complexes. Ainsi toute opération matricielle pourrait servir même si elle parait aussi que la mienne !
Le critère du tri implémenté dans ma source est le décroissant !
Votre 2ème intervention est intéressante : elle suggère une autre conception du tri matricielle.
Merci Monsieur
20 mars 2007 à 18:14
20 mars 2007 à 18:13
Plusieurs remarques.
un, quel intérêt ? une matrice, la plupart du temps, c'est un outil mathématique servant à effectuer, par exemple, une transformation; ce n'est de loin pas le seul usage, mais au final, pourquoi la trier ? et selon quel critère? c'est quoi pour toi, une matrice "triée" ?
Ce qui serait intéressant, ce serait de surcharger l'opérateur > dans une classe de matrices. Ainsi, tu pourrais utiliser des std::map et d'autres conteneurs triés. La signification de > n'a pas besoin d'être mathématiquement correcte ( par exemple, > existe pour Complex bien qu'en réalité ce ne soit la plupart du temps pas possible) ; il suffit juste d'avoir un critére, même idiot, pour que l'ordonnement puisse se faire ( genre return matA[0][0] > matB[0][0] )
voilà :)