voila j'ai le code ci-dessous qui provient d'un bouquin et qui realise
le tri par tas
Code:
/*Fonction de selection de l'indice le plus grand d'un tableau.
Arguments:
- le tableau a trier
- la valeur a inserer
- les limites du tableau
*/
template <typename Type>
void insere_dans_tas(Type* t, Type x, int a, int b)
{
for(int m = 2*a; m <= b; m = 2*a) //boucle examinant le sous-arbre
de t[a]
{
if (m < b) // a a deux fils
if (t[m] < t[m+1]) m++; // on prend le fils le + grand
if (x >= t[m]) //si la valeur a inserer est +
grande
break; //on quitte la boucle
else
{
t[a] = t[m]; //sinon la racine devient t[m]
a = m;
}
}
t[a] = x; //on insere x
}
/*Fonction de creation du tas.
Arguments:
- le tableau a trier
- indice du dernier element du tableau
*/
template <typename Type>
void construis_tas(Type* t, int dernier)
{
for (int i = dernier/2; i >= 1; i--) //boucle de parcours du
tableau a partir du premier
//noeud a considerer
insere_dans_tas(t,t[i],i,dernier); //on insere le noeud dans le
tas
}
/*Fonction de tri par tas.
Arguments:
- le tableau a trier
- indice du dernier element du tableau
*/
template <typename Type>
void tri_par_tas(Type* t, int dernier)
{
construis_tas(t,dernier); //on construis le tas
for (int i = dernier; i >= 1; i--) //boucle de parcours du tableau
{
Type x = t[i]; //on sauve la derniere valeur du
tableau
t[i] = t[1]; //l'element est trie
insere_dans_tas(t,x,1,i-1); //on insere x dans le tas
}
}
il y avait un bel algo fourni avec et jusque la pas de probleme
Sauf qu'un tableau demarre a l'indice 0, et que cette indice n'est pas
pris en compte par cette fonction
Est-ce que jusque la j'ai raison ???
ne dois-je pas lire une premiere fois le tableau avant le tri pour
remonter la valeur la + grande sur la racine de l'arbre ???
merci de votre aide
--
Ceci est une signature automatique de MesNews.
Site : http://arnaud.mesnews.free.fr/
