Aller au contenu

Discussion:Implémentation d'algorithmes classiques/Algorithmes de tri/Tri fusion

Le contenu de la page n’est pas pris en charge dans d’autres langues.
Ajouter un sujet
Un livre de Wikilivres.

Code testés :


le 29/11/2013 : Le code Java corrigé fonctionne mais est loin d'être optimisé ! (je parle de la fonction "fusionner"). En testant ce code, les performances sont moins bonne qu'un tri sélection... Déjà, l'erreur est de cloner le tableau en entier alors que "fusionner" ne s'occupe souvent que d'une sous-partie du tableau. Je propose ici un code qui fonctionne en ne créant un second tableau de la taille nécessaire. Le tri se fait dans ce 2ème tableau et on le recopie à la fin dans le sous-tableau initial.

//fonction qui fusionne 2 sous-parties triées d'un tableau
		public static void fusionner(int tab[], int debut, int milieu, int fin)
	{
	       int [] tab2 = new int[fin-debut+1]; // on va mettre les données dans l'ordre dans tab2

	        int i1 = debut; //indice dans la première moitié de tab
	        int i2 = milieu+1; // indice dans la deuxième moitié de tab
	        int i = 0; //indice dans le tableau tab2
	 
	        while (i1<= milieu && i2 <= fin)
	        {
	                //quelle est la plus petite tête de liste?
	                if(tab[i1] <= tab[i2])
	                {
	                        tab2[i] = tab[i1];
	                        i1++;
	                }
	                else
	                {
	                        tab2[i] = tab[i2];
	                        i2++;
	                }
	                i++;
	        }

	        while(i1<=milieu)  // le reste de la première moitié
	        {
	              	tab2[i]=tab[i1];
	                i1++;
	                i++;
	        }
	        while(i2<=fin) // le reste de la deuxième moitié
	        {
	                tab2[i]=tab[i2];
	                i2++;
	                i++;
	        }

	        //reste à recopier tab2 dans tab
	        for(int j=debut;j<=fin;j++)
	        	tab[j]=tab2[j-debut];
	        	
	}

SebG



Le code en Java me paraît largement foireux, non ? Dans la méthode "fusionner", on initialise t2 comme un tableau d'entier de taille (fin-(milieu+1)). Ensuite, on essaie directement d'accéder à la position (milieu+1), jusqu'à la position (fin).

Par exemple, si milieu == 3, fin == 6, on initialise un tableau de taille 4, puis on essaie d'attaquer directement la position 4, qui n'existe pas, puisque le tableau est indexé de 0 à 3.

C'est mes yeux ? Quelqu'un a testé l'algorithme ? Manproc

Update: j'ai modifié le programme, ça marche chez moi, mais je suis très très loin d'être un expert, et on doit pouvoir faire plus propre. Si ça convient, on peut basculer directement sur l'article.

    public static void triFusion (int [] tab, int debut, int fin){
      int milieu;
      if(debut<fin){
	milieu = (debut+fin)/2;
	triFusion(tab, debut, milieu);
	triFusion(tab, milieu+1, fin);
	fusionner (tab, debut, milieu, fin);
      }
    }

    public static void fusionner(int[] tab, int debut, int milieu, int fin){
      int[] t1 = new int[milieu-debut+1]; // Copy values
      int[] t2 = new int[fin-(milieu)]; // ""
      for (int i = debut; i <= milieu ; i++){
	t1[i-debut] = tab[i];
      }
      for (int i = milieu+1; i <= fin ; i++){
	t2[i-(milieu+1)] = tab[i];
      }
      int i1 =0; // Index for t1
      int i2 =0; // Index for t2
      int i = debut ; // Index for tab
      while (i1 <= (t1.length-1) && i2 <= (t2.length-1)){
	if (t1[i1] <= t2[i2]){
	  tab[i] = t1[i1];
	  i1++;
	} else {
	  tab[i] = t2[i2];
	  i2++;
	}
	i++;
      }

      if (i <= fin){
	while (i1 <= t1.length-1){
	  tab[i] = t1[i1];
	  i++;
	  i1++;
	}
	while (i2 <= t2.length-1){
	  tab[i] = t2[i2];
	  i++;
	  i2++;
	}
      } 
    }
Bravo pour avoir repéré le problème.
J'ai modifié le code : une seule copie du tableau complet est faite, plutôt que deux moitiés, en utilisant la méthode clone().
Ce code fonctionne également.
-- ◄ David L • discuter ► 6 février 2011 à 11:12 (CET)Répondre

Bonjour, Je tenais juste à préciser que le code Python ne fonctionne absolument pas, d'ailleurs j'aimerais rencontrer la personne qui l'a écrite. Passez une agréable journée.