code java qui implementation du tri fusion
public static void triFusion (int [] tab, int début, int fin) { int milieu; if(début < fin) { milieu = (début+fin) / 2; triFusion(tab, début, milieu); triFusion(tab, milieu + 1, fin); fusionner (tab, début, milieu, fin); } } public static void fusionner (int tab[], int début, int milieu, int fin) { int [] old_tab = (int[]) tab.clone(); // tab.clone est tres gourmand en temps d'execution surtout dans un algo recursif // il faudrait passer par un tableau temporaire pour stocker les données triées. // puis recopier la partie triée a la fin de la méthode. int i1 = début; //indice dans la première moitié de old_tab int i2 = milieu + 1; // indice dans la deuxième moitié de old_tab int i = début; //indice dans le tableau tab while (i1 <= milieu && i2 <= fin) { //quelle est la plus petite tête de liste? if(old_tab[i1] <= old_tab[i2]) { tab[i] = old_tab[i1]; i1++; } else { tab[i] = old_tab[i2]; i2++; } i++; } if (i <= fin) { while(i1 <= milieu) // le reste de la première moitié { tab[i] = old_tab[i1]; i1++; i++; } while(i2 <= fin) // le reste de la deuxième moitié { tab[i] = old_tab[i2]; i2++; i++; } } }
