C++Talk.NET

Grand's · Guest

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/

Fabien LE LEZ · Guest

On Mon, 15 Nov 2004 10:24:09 +0100, Grand's <ici (AT) oula (DOT) bas>:

Jean-Marc Bourguet · Guest

Fabien LE LEZ <gramster (AT) gramster (DOT) com> writes:

Fabien LE LEZ · Guest

On 15 Nov 2004 10:37:32 +0100, Jean-Marc Bourguet <jm (AT) bourguet (DOT) org>:

Jean-Marc Bourguet · Guest

Fabien LE LEZ <gramster (AT) gramster (DOT) com> writes:

Jean-Marc Bourguet · Guest

Grand's <ici (AT) oula (DOT) bas> writes:

Grand's · Guest

merci
effectivement c'est bien un exercice demandé par mon prof
tout en sachant que le sujet, tiré d'un bouquin, est fourni avec la
solution
En plus j'ai oublié de lire une phrase ou l'auteur disait que ce tri ne
prenait pas en compte l'indice 0 du tableau.
ce qui explique ma question...desolé
Je voulais juste etre sur de ne pas avoir raté quelque chose

merci

Jean-Marc Bourguet a écrit :

drkm · Guest

Jean-Marc Bourguet <jm (AT) bourguet (DOT) org> writes:

Fabien LE LEZ · Guest

On Tue, 16 Nov 2004 01:11:02 +0100, drkm <usenet.fclcxx (AT) fgeorges (DOT) org>:

kanze@gabi-soft.fr · Guest

Jean-Marc Bourguet <jm (AT) bourguet (DOT) org> wrote

Grand's · Guest

merci beaucoup

[email]kanze (AT) gabi-soft (DOT) fr[/email] a formulé la demande :

drkm · Guest

Fabien LE LEZ <gramster (AT) gramster (DOT) com> writes:

kanze@gabi-soft.fr · Guest

drkm <usenet.fclcxx (AT) fgeorges (DOT) org> wrote