16 octobre 2013
3
16
/10
/octobre
/2013
14:50
Principe:
Ce tri suit le paradigme diviser pour regner le principe est le suivant :
- On divise en deux moitiés la liste que l'on veut trier
- On trie chacune d'elle
- On fusionne les deux moitiés obtenues pour reconstruire la liste triée
Pseudo code (source Wikipedia)
fonction scinder(liste0) : si longueur(liste0) <= 1, renvoyer le couple (liste0, liste_vide) sinon, soient e1 et e2 les deux premiers éléments de liste0, et reste le reste de liste0 soit (liste1, liste2) = scinder(reste) renvoyer le couple de listes (liste de tête : e1 et de queue : liste1, liste de tête : e2 et de queue : liste2) fonction fusionner(liste1, liste2) : si la liste1 est vide, renvoyer liste 2 sinon si la liste2 est vide, renvoyer liste 1 sinon si tête(liste 1) <= tête(liste2), renvoyer la liste de tête : tête(liste1) et de queue : fusionner(queue(liste1),liste2) sinon, renvoyer la liste de tête : tête(liste2) et de queue : fusionner(liste1,queue(liste2)) fonction triFusion(liste0) : si longueur(liste0) <= 1, renvoyer liste0 sinon, soit (liste1, liste2) = scinder(liste0) renvoyer fusionner(triFusion(liste1), triFusion(liste2))
Complexité: Θ(NlogN).
Sa complexité temporelle pour une entrée de taille n est de l'ordre de nlog n
Implémentation en java
Class TriFusion:
package pisix.ag.trifusion; import java.util.ArrayList; public class TriFusion { ArrayList<Integer> listeElementATrier; public TriFusion(){ } public TriFusion(ArrayList<Integer> listeElementATrier){ this.listeElementATrier=listeElementATrier; } public ArrayList<Integer> getListeElementATrier() { return listeElementATrier; } public void setListeElementATrier(ArrayList<Integer> listeElementATrier) { this.listeElementATrier = listeElementATrier; } public void fusion(ArrayList<Integer>liste, int debut1, int fin1, int fin2){ liste=listeElementATrier; ArrayList<Integer> liste2 = new ArrayList<Integer>(); int debut2=fin1+1; int compteur1=debut1; int compteur2=debut2; int i; //copie des éléments du début de tableau for(int k=0;k<(fin1-debut1+1);k++){ liste2.add(0); } for(i=debut1;i<=fin1;i++){ liste2.set(i-debut1, liste.get(i)); } //fusion des deux tableaux for(i=debut1;i<=fin2;i++){ if(compteur1==debut2)//éléments du 1er tableau tous utilisés { break;//Tous les éléments ont donc été classé } else if(compteur2==(fin2+1))//éléments du 2nd tableau tous utilisés { //copie en fin de tableau des éléments du 1er sous tableau liste.set(i, liste2.get(compteur1-debut1)); compteur1++; } else if (liste2.get(compteur1-debut1)<liste.get(compteur2)) { //ajout d'1 élément du 1er sous tableau liste.set(i, liste2.get(compteur1-debut1)); compteur1++; } else{ //copie de l'élément à la suite du tableau liste.set(i, liste.get(compteur2)); compteur2++; } } } void triFusionAux(ArrayList<Integer> liste,int debut,int fin){ if(debut!=fin)//condition d'arrêt { int milieu=(debut+fin)/2; triFusionAux(listeElementATrier, debut, milieu); triFusionAux(listeElementATrier, milieu+1, fin); fusion(listeElementATrier,debut,milieu,fin); } } public ArrayList<Integer>tri(){ if(listeElementATrier.size()>0) triFusionAux(listeElementATrier, 0, listeElementATrier.size()-1); return listeElementATrier; } }
Class Main:
package pisix.ag.trifusion; import java.util.ArrayList; import pisix.ag.tribulle.TriFusion; public class RunTriFusion { public static void main(String[] args) { // TODO Auto-generated method stub ArrayList<Integer> liste=new ArrayList<Integer>(); //Generation d'un tableau de maniere aléatoire de 150 000 éléments for(int i =0; i<150000;i++){ liste.add(i); liste.set(i, (int) (Math.random()*(149999-1)+1)); } //On passe la liste à trier à notre constructeur TriFusion tri1 = new TriFusion(liste); ArrayList<Integer> listeTriee; long deb = System.currentTimeMillis(); //Lancement du tri listeTriee = tri1.tri(); long fin = System.currentTimeMillis()-deb; System.out.println("Apres le tri Fusion les valeurs du Tableau sont :"); for(int list : listeTriee){ System.out.println(list); } //On affiche le temps d'éxécution de l'algo System.out.println("Temps d'execution en milliseconde : "+fin); } }
Courbe expérimentale:
Le graphique ci-dessous montre la progression du nombres d'instruction(temps (ms)) en fonction de la taille(Nombre d'éléments)
C'est tout pour le moment ....