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

Code testés :

• Caml (2) : Zandr4^[Kupopo ?] 24 avril 2010 à 13:11 (CEST)
• C : Zandr4^[Kupopo ?] 24 avril 2010 à 13:11 (CEST)

Code Java

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)

Code Pyhton

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.