Tri par fusion (Merge Sort)

Version imprimable

02/05/2015, 18h22
saimer

Tri par fusion (Merge Sort)

Bonjour,

j'ai un tableau d'objets (créés à partir d'une classe) que je veux trier, suivant la valeur d'un attribut de la classe, en utilisant l'un des algorithmes de tri connus par leur complexité réduite.

La recherche sur internet m'a préconisée d'utiliser le tri par fusion (Merge Sort) dont la complexité est O(n log n).

J'ai essayé d'implémenter cet algorithme en Java, mais je n'ai pas réussi à le faire. J'ai aussi cherché sur Internet vainement car les programmes proposés sont incomplets (juste des fragments de code).

Quelqu'un pourrait m'aider par un code fonctionnel ?

Remerciement.
02/05/2015, 21h42
thelvin

Hello,

......

Et, euh....

Collections.sort() ?

C'est pas tout à fait un merge sort, c'est un petit peu amélioré, mais en termes de complexité réduite c'est plutôt bon.

le code ci-après est une implémentation du Tri par fusion:

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package sort;
import java.util.Random;
public class MergeSort {
	 int data[];
    private Random gen = new Random();
 
    public MergeSort() {
    	data= new int []{3,4,1,2,0};
	}
	public MergeSort(int length) {
    data=new int[length];
    for(int i = 0;i<data.length;i++){
    	data[i]= 1+gen.nextInt(99);
    }
    }
	public void sort(){
		sortArray(0,data.length-1);
	}
	private void sortArray(int low, int high){
		if((high - low)>=1){
			int m = (low + high)/2;
			sortArray(low,m);
			sortArray(m+1,high);
			merge(low,m,high);
 
 
		}
 
	}
	private void merge(int l,int m, int h ){
		int [] temp= new int[data.length];
		int left = l;
		int right=m+1;
		int index =l;
		while((left<=m)&&(right <= h) ){
		if(data[right]<data[left]){
			temp[index++]=data[right++];
		}
		else{
			temp[index++]=data[left++];
 
		}
		}
		if(left==m+1){
		while(right<=h)
			temp[index++]=data[right++];
		}
		else
		{
			while(left<=m)
				temp[index++]=data[left++];
		}
 
 
		for(int i=l;i<=h;i++)
			data[i]=temp[i];
	}
 
 
	public void afficher(int l, int h){
		for(int k=l;k<h;k++)
		System.out.print(data[k]+" ");
		System.out.println();
	}
 
	public static void main(String[] args) {
		int n= 10;
		MergeSort ms = new MergeSort(n);
		ms.afficher(0,ms.data.length);
		ms.sort();
		System.out.println("fin tri ...!");
		ms.afficher(0,ms.data.length);
		}
 
 
}

04/05/2015, 10h54
eulbobo

Citation:

Envoyé par saimer

j'ai un tableau d'objets (créés à partir d'une classe) que je veux trier, suivant la valeur d'un attribut de la classe, en utilisant l'un des algorithmes de tri connus par leur complexité réduite.

Tu as plein de possibilités pour faire ça.

Les deux bonnes possibilités sont les suivantes :
- Faire en sorte que ta classe implémente Comparable ce qui permet à chaque élément de pouvoir être trié automatiquement par rapport aux autres, puis tu utilises la fonction Arrays.sort(<ton tableau>)
- Créer une classe qui étend Comparator<TaClasse>, et appeler la fonction Arrays.sort(<ton tableau>, <une instance de ton comparator>)

Après, si le but est de faire un algo de tri, tu peux t'inspirer de ce qui se trouve dans les classes Arrays et Collections (mais je ne suis pas un expert de l'algo de tri, donc je ne pourrais pas t'aider plus )
29/05/2015, 12h13
saimer

Citation:

Envoyé par eulbobo

Tu as plein de possibilités pour faire ça.

Les deux bonnes possibilités sont les suivantes :
- Faire en sorte que ta classe implémente Comparable ce qui permet à chaque élément de pouvoir être trié automatiquement par rapport aux autres, puis tu utilises la fonction Arrays.sort(<ton tableau>)
- Créer une classe qui étend Comparator<TaClasse>, et appeler la fonction Arrays.sort(<ton tableau>, <une instance de ton comparator>)

Après, si le but est de faire un algo de tri, tu peux t'inspirer de ce qui se trouve dans les classes Arrays et Collections (mais je ne suis pas un expert de l'algo de tri, donc je ne pourrais pas t'aider plus )

Bonjour,

merci pour votre réponse.

Voila, j'ai utilisé "Comparable", j'ai donc redéfini la méthode dans ma classe et ça marche.

Maintenant, j'ai un autre problème.

Au fait, dans ma classe A j'ai deux attributs; att1 de type double et att2 de type complexe (d'une autre classe B qui est à son tour composeé de deux attribut simple.

Je veux faire le tri des objets de la classe A suivant la valeur de att1 et chacun des attributs de la classe B. Les résultats doivent être sauvegardé séparément.

PS. j'ai redéfini la méthode compareTo dans A suivant att1 mais j'ai pas pu le faire pour le reste.

Merci pour votre aide.
29/05/2015, 14h00
eulbobo

Tu veux trier des éléments de ta classe A.

Du coup, dans ta méthode de comparaison, tu compares :
this.att1 avec other.att1
this.att2.variable1DeB avec other.att2.variable1DeB
this.att2.variable2DeB avec other.att2.variable2DeB
etc...

Bref, dans la comparaison des éléments A entre eux, tu utilises les attributs de A, que ce soit des types simples ou des objects.
Tu peux aussi implémenter Comparable sur ta classe B, et du coup, ta méthode de comparaison de A pourra se faire en comparant
this.att1 avec other.att1
this.att2.compareTo(other.att2)

L'avantage, c'est que si ta classe B évolue, tu n'auras pas à changer le code dans A pour prendre en compte les nouveaux éléments dans B pour le tri
29/05/2015, 14h47
hwoarang

Citation:

Envoyé par saimer

Je veux faire le tri des objets de la classe A suivant la valeur de att1 et chacun des attributs de la classe B. Les résultats doivent être sauvegardé séparément.

Ce que tu demandes n'est pas clair. Soit tu veux avoir 2 listes avec tes objets classés selon 2 criteres differents. Dans ce cas, il ne faut pas utiliser Comparable mais plutot Comparator:
https://docs.oracle.com/javase/8/doc...il.Comparator-

Soit tu veux classer selon 2 parametres differents (par exemple nom de famille puis prenom).
Dans ce cas, il faut faire:
- Si nom1 == nom2 renvoyer prenom1.compareTo(prenom2)
- sinon, renvoyer nom1.compareTo(nom2)
29/05/2015, 15h25
saimer

Citation:

Envoyé par hwoarang

Ce que tu demandes n'est pas clair. Soit tu veux avoir 2 listes avec tes objets classés selon 2 criteres differents. Dans ce cas, il ne faut pas utiliser Comparable mais plutot Comparator:
https://docs.oracle.com/javase/8/doc...il.Comparator-

Soit tu veux classer selon 2 parametres differents (par exemple nom de famille puis prenom).
Dans ce cas, il faut faire:
- Si nom1 == nom2 renvoyer prenom1.compareTo(prenom2)
- sinon, renvoyer nom1.compareTo(nom2)

de façon plus précise, voici mes déclarations :

public class A implements Comparable<A> {

private a1 B;

private ArrayList<C> listC = new ArrayList <C> ();

...

@Override
public int compareTo(A otherA) {

// Déclaration de la comparaison selon a1

}

}

public class B implements Cloneable{

private double b1;
private int b2 ;

.....
}

public class C {

private double c1;
...
}

J'ai un tableau "tab" d'objets de la classe "A".
ArrayList<A> tab = new ArrayList<A>();

Je veux trier les objets de "tab", de façon séparée, selon l'attribut b1 et chacun des attribut de listC.

____________________________

Merci
29/05/2015, 15h55
eulbobo

Donc comme je disais :
- implémente Comparable dans B
- dans l'implémentation Comparable de A, compare les deux variables de type B entre elles (en utilisant Comparable)

Par contre, la comparaison d'éléments en fonction d'éléments dans une ArrayList n'a pas de sens parce qu'on ne sait pas :
- est-ce que l'ordre a un sens?
- est-ce que les doublons potentiels ont un sens?
- comment comptes-tu comparer les éléments de deux listes deux à deux sachant qu'elles ne sont pas forcement dans le même ordre avec les même éléments ?

Par exemple
Liste 1, tu as les valeurs C D A
Liste 2, tu as les valeurs D A B
Comment tu les compares pour savoir laquelle vient avant l'autre?
29/05/2015, 16h23
saimer

Citation:

Envoyé par eulbobo

Donc comme je disais :
- implémente Comparable dans B
- dans l'implémentation Comparable de A, compare les deux variables de type B entre elles (en utilisant Comparable)

Par contre, la comparaison d'éléments en fonction d'éléments dans une ArrayList n'a pas de sens parce qu'on ne sait pas :
- est-ce que l'ordre a un sens?
- est-ce que les doublons potentiels ont un sens?
- comment comptes-tu comparer les éléments de deux listes deux à deux sachant qu'elles ne sont pas forcement dans le même ordre avec les même éléments ?

Par exemple
Liste 1, tu as les valeurs C D A
Liste 2, tu as les valeurs D A B
Comment tu les compares pour savoir laquelle vient avant l'autre?

Pour les éléments de "listC":
- y a pas de doublons.
- ils sont dans le même ordre, c.à.d, si on considère deux objet 01 et 02 et que la "listC" a 3 élément on a forcément le même ordre pour les objets;
O1 : A B C et O2 : A B C.

Merci
29/05/2015, 16h27
eulbobo

Ok pour l'ordre dans la liste...

mais du coup, comment on fait pour comparer les éléments de la liste s'il ne contiennent pas les mêmes éléments ou le même nombre d'éléments?

Exemple avec ces trois listes :
liste 1 : A D
liste 2 : B C
liste 3 : E
Laquelle doit être considérée comme la première si on devait les classer ?
29/05/2015, 16h40
saimer

Citation:

Envoyé par eulbobo

Ok pour l'ordre dans la liste...

mais du coup, comment on fait pour comparer les éléments de la liste s'il ne contiennent pas les mêmes éléments ou le même nombre d'éléments?

Exemple avec ces trois listes :
liste 1 : A D
liste 2 : B C
liste 3 : E
Laquelle doit être considérée comme la première si on devait les classer ?

Tous les objets du tableau "tab" ont le même nombre d'éléments de "listC" et dans le même ordre.

Exemple: soient trois objets O1, O2, et O3 de "tab" ayant comme élément de "listC" A B C.

O1 (A=1, B=6, C=7)
O2 (A=4, B=3, C=1)
O3 (A=3, B=11, C=5)

Le tri, si on le considère ascendant,
- selon l'attribut "A" donne : O1 O3 O2,
- selon "B" donne : O2 O1 O3
- et enfin selon "C" donne : O2 O3 O1
29/05/2015, 16h56
eulbobo

Je n'ai RIEN COMPRIS de ton exemple

Par contre, j'ai compris que toutes tes listes avaient la même taille, sans doublons, et déjà classés dans l'ordre.
Tu as dans ton code une List<C>, c'est celle-là qui m'intéresse.

Prenons 4 instances de la classe C que nous allons nommer elementC1, elementC2, elementC3, elementC4 (sachant que je les ai déclarés dans l'ordre ascendant, donc elementC1 < elementC2 < elementC3 < elementC4)

Imaginons les deux List<C> suivantes :
List<C> premiereListe qui contient les éléments suivants : elementC1 et elementC4
List<C> deuxièmeListe qui contient les éléments suivants : elementC2 et elementC3

Dans quelle ordre ces deux listes doivent-ils apparaître selon toi? (ce qui me permettra de pouvoir te dire comme faire ton comparateur)
29/05/2015, 17h20
saimer

Citation:

Envoyé par eulbobo

Je n'ai RIEN COMPRIS de ton exemple

Par contre, j'ai compris que toutes tes listes avaient la même taille, sans doublons, et déjà classés dans l'ordre.
Tu as dans ton code une List<C>, c'est celle-là qui m'intéresse.

Prenons 4 instances de la classe C que nous allons nommer elementC1, elementC2, elementC3, elementC4 (sachant que je les ai déclarés dans l'ordre ascendant, donc elementC1 < elementC2 < elementC3 < elementC4)

Imaginons les deux List<C> suivantes :
List<C> premiereListe qui contient les éléments suivants : elementC1 et elementC4
List<C> deuxièmeListe qui contient les éléments suivants : elementC2 et elementC3

Dans quelle ordre ces deux listes doivent-ils apparaître selon toi? (ce qui me permettra de pouvoir te dire comme faire ton comparateur)

On sais pas bien compris!

Exactement, on intéresse au tri des objets selon les instance de "listC"

J'explique plus mon exemple. On considère 3 objets O1, O2 et O3, chacun a 3 instances de la classe C.

Pour l'objet O1 on a, par exemple, les valeurs des trois instances comme suit : 1 6 7 .
Pour l'objet O2 on a les valeur 4 3 1
et pour O3 on a 3 11 5.

Le tri, si on le considère ascendant,
- selon la première instance de C donne : O1 O3 O2,
- selon la deuxième instance de C donne : O2 O1 O3
- et enfin selon la troisième instance donne : O2 O3 O1

est-il claire mon exemple ?
29/05/2015, 17h23
saimer

Citation:

Envoyé par hwoarang

Ce que tu demandes n'est pas clair. Soit tu veux avoir 2 listes avec tes objets classés selon 2 criteres differents. Dans ce cas, il ne faut pas utiliser Comparable mais plutot Comparator:
https://docs.oracle.com/javase/8/doc...il.Comparator-

Soit tu veux classer selon 2 parametres differents (par exemple nom de famille puis prenom).
Dans ce cas, il faut faire:
- Si nom1 == nom2 renvoyer prenom1.compareTo(prenom2)
- sinon, renvoyer nom1.compareTo(nom2)

OUI, effectivement je veux avoir des listes avec tes objets classés selon des criteres differents. Mais je n'ai pas pu le faire
07/06/2015, 14h24
saimer

Tri personnalisé des objets en utilisant Comparator

Citation:

Envoyé par saimer

OUI, effectivement je veux avoir des listes avec tes objets classés selon des criteres differents. Mais je n'ai pas pu le faire

Bonjour,

je suis vraiment BLOQUE sur mon problème de tri d'objets.

De façon plus pratique, j'ai une classe Produit décrivant un ensemble de produits par l'attribut libelleProd de type simple et listQualiteProd de type d'une autre classe Qualite. L'attribut "listQualiteProd" décrit un ensemble de qualités relatives à un produit donné tel que le coût, disponibilité en stock, etc. L'ensemble de qualités peut évoluer, c'est pourquoi j'ai utilisé une liste.

Voici mes déclarations :

public class Produit {

private String libelleProd;

private ArrayList<Qualite> listQualiteProd = new ArrayList <Qualite> ();

...

}

public class Qualite {

private String nomQualite ;
private double valeurQualite;
...

}

Voici un exemple de 3 produits. On considère que chaque produit a deux qualité (cout et dispo en stock) :

Produit 1 : montre; (cout = 100, dispo=12)
Produit 2 : table; (cout= 13, dispo=39)
Produit 3 : Stylo; (cout= 5, dispo=96)

J'ai un tableau "tab" d'objets de la classe Produit.
ArrayList<Produit> tab = new ArrayList<Produit>();

Je veux trier les objets de "tab", selon l'attribut "libelleProd" et chacun des attributs de listQualiteProd.

J'ai trouvé sur Internet comment utiliser "Comparator" pour le tri personnalisé sur des attributs d'une classe
http://examples.javacodegeeks.com/co...rator-example/

mais pour une liste, comme dans mon cas, j'ai du mal à le faire.

Merci pour votre aide.
09/06/2015, 10h37
eulbobo

Citation:

Envoyé par saimer

Voici un exemple de 3 produits. On considère que chaque produit a deux qualité (cout et dispo en stock) :

Problème de conception Objet : si ton produit a des qualités précises, elles doivent exister en tant que propriétés de ta classe.
Utiliser une ArrayList, ça veut dire que ta classe "contient" des éléments. Ou pas, vu qu'une List n'a pas de taille prédéfinie obligatoire !

Si tes "qualités" deviennent des attributs/propriétés de ta classe, le tri sera beaucoup plus intuitif.
09/06/2015, 11h54
saimer

Citation:

Envoyé par eulbobo

Problème de conception Objet : si ton produit a des qualités précises, elles doivent exister en tant que propriétés de ta classe.
Utiliser une ArrayList, ça veut dire que ta classe "contient" des éléments. Ou pas, vu qu'une List n'a pas de taille prédéfinie obligatoire !

Si tes "qualités" deviennent des attributs/propriétés de ta classe, le tri sera beaucoup plus intuitif.

Les qualités d'un objet peuvent évoluer durant le temps. Ce qui ma poussé à utiliser un ArrayList, c'est pour rendre les choses dynamiques.
09/06/2015, 12h01
eulbobo

Citation:

Envoyé par saimer

Les qualités d'un objet peuvent évoluer durant le temps. Ce qui ma poussé à utiliser un ArrayList, c'est pour rendre les choses dynamiques.

Le coût d'un produit ne va pas disparaître... C'est pourtant une "évolution" possible que tu décris en le mettant dans une ArrayList.
Et à ce rythme là, pourquoi ne pas juste faire un Objet "générique" contenant une HashMap d'objets ? Ca serait totalement générique (mais totalement inutilisable)

Si les caractéristiques de ton produit évoluent, c'est qu'il y a deux possibilités :
- ton produit n'est pas assez bien décrit pour l'instant : a toi de tout de suite rajouter les qualités qui manquent
- tu ne peux pas le décrire car les caractéristiques dépendent du type d'objet : il faut dans ce cas utiliser l'héritage pour que chaque classe fille ajoute en précision à la classe mère

Fuseau horaire GMT +2. Il est actuellement 07h49.