tri decroissant tableau à 2 dimensions

Version imprimable

09/06/2009, 14h23
flora806

tri decroissant tableau à 2 dimensions
Bonjour,
Code:

1 2 3 ClientMatrix [clientID][articleID]= prixPayed;
je voudrais trier ce tableau d'entiers à 2 dimensions par ordre décroissant. je souhaite récupérer pour chaque client les 10 plus cher articles achetés.

Quelqu'un aurait une idée?

Merci

Code:

1
2
3
4
5
6
7
for (int j =0; j<ClientMatrix.length; j++ ){
    System.out.println("Client "+j+" :");
    Arrays.sort(ClientMatrix[j]);
    for( int i=ClientMatrix[j].length-1; i>=0 && i >= ClientMatrix[j].length-10; i--){
        System.out.println(ClientMatrix[j][i]);
    }
}

édition: les résultats n'étaient pas affichés par ordre décroissant

09/06/2009, 14h56
Ivelios

Juste pour information, 3 manières de triés un tableau :

---->trie à bulle, tu parcours le tableau de gauche à droite et tu fais remonter le plus grand nombre à chaque fois. Parcours x fois le tableau, x =taille du tableau

---->Un méthode qui consiste à diviser le tableau en 2 puis en 2 puis en 2 ... Quand tu les divises en 2, tu mets d'un coté les plus grand nombres et de l'autre coté les plus petit. Méthode récursive.

---->La méthode de la mort, ne marche pas à tous les coup donc à consommer avec modération. tu peux trier en parcourant seulement 3 fois le tableau:

-1, tu recupère le plus petit et le plus grand nombre qui sont dans le tableau( tab1)
puis tu crées un autre tableau (tab2) qui à pour taille (plusGrand-PlusPetit)

-2 tu parcours tab1 et tu incrementes les cases de tab2 à chaque fois qu'il y a une occurence. exemple :
Si tab1 = 1|1|4|3|1|4 --->trois 1, zero 2, un 3 et deux 4
alors tab2 = 3|0|1|2

-3 tu parcours tab2 et tu remets les nombres dans un 3eme tableau en fonction de leurs occurences. exemple :
Si tab2 = 3|0|1|4 trois 1, zero 2, un 3 et deux 4
Alors tab3 1|1|1|3|4|4

Tab3 = Tab1 mais trié

Pourquoi ne marche pas à tous les coup ? Si dans ton tableau il y a un nombre = 999999999999999 cela implique de créer un tableau tab2 avec 999999999999999 cases... pas la peine d'expliquer le problème plus loin ;)
09/06/2009, 14h57
flora806

Merci Uther pour ta réponse,
je viens de tester ton code, ça m'affiche toutes les valeurs de la matrice mais qui ne sont pas triées selon l'ordre décroissant.
Au lieu de faire un print, est-ce que je pourrais copier les 10 articles les + chers ainsi que leurs prix dans un autre tableau et le retourner?

Merci :)
09/06/2009, 15h06
flora806

Merci Ivelios,
mais c'est un peu compliqué pour moi, comme je suis débutante :?

Citation:

Envoyé par Ivelios

Juste pour information, 3 manières de triés un tableau :

---->trie à bulle, tu parcours le tableau de gauche à droite et tu fais remonter le plus grand nombre à chaque fois. Parcours x fois le tableau, x =taille du tableau

---->Un méthode qui consiste à diviser le tableau en 2 puis en 2 puis en 2 ... Quand tu les divises en 2, tu mets d'un coté les plus grand nombres et de l'autre coté les plus petit. Méthode récursive.

---->La méthode de la mort, ne marche pas à tous les coup donc à consommer avec modération. tu peux trier en parcourant seulement 3 fois le tableau:

-1, tu recupère le plus petit et le plus grand nombre qui sont dans le tableau( tab1)
puis tu crées un autre tableau (tab2) qui à pour taille (plusGrand-PlusPetit)

-2 tu parcours tab1 et tu incrementes les cases de tab2 à chaque fois qu'il y a une occurence. exemple :
Si tab1 = 1|1|4|3|1|4 --->trois 1, zero 2, un 3 et deux 4
alors tab2 = 3|0|1|2

-3 tu parcours tab2 et tu remets les nombres dans un 3eme tableau en fonction de leurs occurences. exemple :
Si tab2 = 3|0|1|4 trois 1, zero 2, un 3 et deux 4
Alors tab3 1|1|1|3|4|4

Tab3 = Tab1 mais trié

Pourquoi ne marche pas à tous les coup ? Si dans ton tableau il y a un nombre = 999999999999999 cela implique de créer un tableau tab2 avec 999999999999999 cases... pas la peine d'expliquer le problème plus loin ;)
09/06/2009, 15h25
Ivelios

pour le tri à bulle : ici
Après, pour n'avoir que les 10 premiers il suffit de regarder les 10 premières cases du tableau.

Citation:

Au lieu de faire un print, est-ce que je pourrais copier les 10 articles les + chers ainsi que leurs prix dans un autre tableau et le retourner?

Rien ne te l'empèche

Merci pour vos réponses.
ça marche maintenant avec ce code (j'ai changé quand même le || en &&), j'ai besoin juste de retourner en résultat les données triées dans un autre tableau au lieu de faire un print.
Citation:
Envoyé par Uther
Code:

1 2 3 4 5 6 7 for (int j =0; j<ClientMatrix.length; j++ ){ System.out.println("Client "+j+" :"); Arrays.sort(ClientMatrix[j]); for( int i=ClientMatrix[j].length-1; i>=0 && i >= ClientMatrix[j].length-10, i--){ System.out.println(ClientMatrix[j][i]); } }
édition: les résultats n'étaient pas affichés par ordre décroissant

09/06/2009, 15h41
Uther

Certes on peut implémenter soi même un tri a bulle mais étant donné que Java fourni déjà Arrays.sort qui est certainement plus efficace qu'un banal bubble-sort, autant l'utiliser.

L'intérêt du bubble-sort en dehors des cours d'algo/programmation est quasi nul.

J'ai édité mon code pour qu'il retourne les résultats dans l'ordre décroissant. Bien sur j'ai fait un System.out.println() pour afficher les résultats sur la console, mais on peut faire ce que l'on souhaite à la place.

pour compléter le code d'Uther

Code:

1
2
3
4
5
6
7
8
9
10
public Object[] getTableau(){
Object[][] result = new Object[??][10];
for (int j =0; j<ClientMatrix.length; j++ ){
    System.out.println("Client "+j+" :");
    Arrays.sort(ClientMatrix[j]);
    for( int i=ClientMatrix[j].length-1; i>=0 &&  i >= ClientMatrix[j].length-10; i--){
        result[j][i] =  ClientMatrix[j][i]);
    }
return result;
}

il marche bien ce code, merci.
Par contre ici on ne garde plus les réf d'origine des articles achetés par les clients, puisque le i recupère plutôt la taille "ClientMatrix[j].length-1...".
on ne peut pas avoir dans le "result" ces réf?
Citation:
Envoyé par Ivelios
pour compléter le code d'Uther
Code:

1 2 3 4 5 6 7 8 9 10 public Object[] getTableau(){ Object[][] result = new Object[??][10]; for (int j =0; j<ClientMatrix.length; j++ ){ System.out.println("Client "+j+" :"); Arrays.sort(ClientMatrix[j]); for( int i=ClientMatrix[j].length-1; i>=0 && i >= ClientMatrix[j].length-10; i--){ result[j][i] = ClientMatrix[j][i]); } return result; }

09/06/2009, 17h01
bigbear19

Salut,

Je ne suis pas sûr de comprendre ton problème, mais le i référence le articleID définit dans ton premier post.

Code:

ClientMatrix [clientID][articleID] = prixPayed;
09/06/2009, 17h16
flora806
oui, tout à fait, ça référence normalement articleID.
mais par exemple si je veux retourner les 10 articles les + chers par client, je fais (dans une autre méthode):
Code:

1 2 3 4 5 6 7 for(int i = 0 ; i < result[clientID].length ; i++) { articleList.add(i); System.out.println("article "+i+" :"); }
j'ai pas les bonnes références des articles pour ce client, j'ai plutôt une sorte d'indices...

je m'explique, comme j'ai 1000 articles sur ma matrice, quand je retourne "articleList" il m'affiche avec ce code par exemple:

[990, 991, 992, 993.....999] (10 articles)

ça ne correspond pas aux vrais ID des articles.

Citation:

Envoyé par bigbear19

Salut,

Je ne suis pas sûr de comprendre ton problème, mais le i référence le articleID définit dans ton premier post.

Code:

ClientMatrix [clientID][articleID] = prixPayed;
09/06/2009, 17h36
bigbear19

Exact (j'avais oublié le tri...)
Du coup, une première idée (sans avoir trop réfléchi à la question) serait de créer une table de hashage associant un articleID à un prix.
Tu pourrais, si besoin, optimiser l'espace mémoire en ne stockant que les 10 articles les plus chers, mais il faudrait dans ce cas, implémenter un algo de tri perso.
10/06/2009, 08h42
Ivelios

Un idée en vrac, avec un BDD tu aurais stocké tes données dans une table client et une table produit avec un lien entre elles.
Puis, plus cas faire une requête du style :

Code:

SELECT TOP 10 article FROM TabArticle,TabClient WHERE TabClient.client = 'Mr.X' ORDER BY TabArticle.prix DESC;

C'était juste une idée au passage

oui, merci.
là j'essaie de passer par une hashMap, voir si je peux récupérer les 10 articlesID triés par client. si ça marche pas je passerai peut être par une BD.

voilà ce que je fais, j'essaie de faire un tri d'une hashMap selon les values:

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
36
 
........
// priceMap contient <articleID,price>
 
 HashMap<Integer,Double> priceMap = getMapClient(clientID);
 
Set set = new TreeSet (   
	             new Comparator (  )   
	              {   
	                 public int compare (  Object o1, Object o2  )   
	                  {   
	                     Map.Entry e1 =  ( Map.Entry ) o1;  
	                     Map.Entry e2 =  ( Map.Entry ) o2;  
 
 
 
	                     Double d1 =  ( Double ) e1.getValue (  ) ;  
	                     Double d2 =  ( Double ) e2.getValue (  ) ;  
 
 
 
	                     return d1.compareTo (  d2  ) ;  
	                  }   
	              }   ) ;  
 
 
 
	         set.addAll (  priceMap.entrySet (  )   ) ;  
 
 
 
	         for  (  Iterator iter = set.iterator (  ) ; iter.hasNext (  ) ;  )   
	          {   
	             Map.Entry entry =  ( Map.Entry ) iter.next (  ) ;  
	             System.out.println (  entry.getKey (  )  + " = " + entry.getValue (  )   ) ;  
	          }

Mais ce code m'affiche les articles triés selon le prix dans un ordre croissant. En +, si 2 articles ont le même prix, il m'en affiche juste un seul.

je vois pas encore comment changer ce comparator pour obtenir les 10 top articles par client. 8O

Euh...j'avoue ne pas trop comprendre la façon dont tu te sers de la HashMap.
Voici l'algo que j'avais en tête (qui est assez fastidieux...):

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public Object[] getTableau() {
   Object[][] result = new Object[??][10];
   // la clé est le prix de l'article, la valeur est l'articleID
   HashMap hm;
   for (int j = 0;  j < ClientMatrix.length; j++) {
      // cette méthode remplit la HashMap avec les 10 articles les plus chers
      hm = initHashMap(ClientMatrix[j]);
      Arrays.sort(ClientMatrix[j]);
      for( int i = ClientMatrix[j].length-1; i >= 0 &&  i >= ClientMatrix[j].length - 10; i--) {
         result[j][i] =  hm.get(ClientMatrix[j][i]);
      }
   }
   return result;
}

Code:

1
2
3
4
5
6
7
8
9
10
11
public HashMap<int, int> intiHashMap(int[] tab) {
   HashMap<int, int> hm = new HashMap<int, int>(10);
   int prixMinimum;
   // tu remplis la HashMap avec les 10 premiers éléments du tableau
   // tu stockes le prix du moins cher dans prixMinimum
   // tu parcours le reste du tableau
      // si un prix est supérieur à la variable précédente
         // tu parcours la HashMap pour supprimer le moins cher et le remplacer par
         // l'élément courant du tableau, puis tu mets à jour prixMinimum
   // tu retournes la HashMap
}

En espérant que ça puisse t'aider ;)

10/06/2009, 11h58
Celeborn

Citation:

Envoyé par Ivelios

Juste pour information, 3 manières de triés un tableau :

bien plus que ça !
10/06/2009, 13h15
Ivelios

Citation:

Envoyé par Celeborn

bien plus que ça !

Oups... je ne connais que trois façon... :triste:
10/06/2009, 14h02
zorm

Citation:

Envoyé par Ivelios

Oups... je ne connais que trois façon... :triste:

Pour ta culture, les algorithmes de tri sont souvent étudiés plus en détail lors de cours sur la complexité.