code java qui implementation du tri fusion code example

Example: 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++;
		}
	}
}