EFFECTUER UN TRI DE VALEURS ENTIÈRES (DEV-C++4.1)
cs_Mat06
Messages postés
37
Date d'inscription
jeudi 15 janvier 2004
Statut
Membre
Dernière intervention
22 octobre 2004
-
18 avril 2004 à 15:52
cs_djl Messages postés 3011 Date d'inscription jeudi 26 septembre 2002 Statut Membre Dernière intervention 27 novembre 2004 - 20 avril 2004 à 22:35
cs_djl Messages postés 3011 Date d'inscription jeudi 26 septembre 2002 Statut Membre Dernière intervention 27 novembre 2004 - 20 avril 2004 à 22:35
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/22049-effectuer-un-tri-de-valeurs-entieres-dev-c-4-1
https://codes-sources.commentcamarche.net/source/22049-effectuer-un-tri-de-valeurs-entieres-dev-c-4-1
20 avril 2004 à 22:35
c++ standard reste encore comptatible avec c ansi, c'est juste qq synthaxe du c pre ansi qui ont ete supprimer
par contre certainee specificité de c99 ne sont pas compatible avec c++
20 avril 2004 à 22:13
20 avril 2004 à 21:23
franchement, c ou c++ je conseil d'acquerir les bases avec un livre (k&r ansi pour le c et stroupstrup 3e editions pour le c++)
20 avril 2004 à 21:06
20 avril 2004 à 19:13
20 avril 2004 à 18:00
20 avril 2004 à 09:23
19 avril 2004 à 22:52
19 avril 2004 à 22:49
19 avril 2004 à 22:48
cout << "bonjour";
while(1)
{
calcul_quelconque();
getch();
}
ce genre de truc, il arrive que bonjour ne s'affiche pas.
19 avril 2004 à 22:42
19 avril 2004 à 22:34
sinon le return 0 n'est pas obligatoire en c++, mais bon, ca depend malheuresement encore des compilos
19 avril 2004 à 22:22
Je sais pas trop l'étendu, mais comme ca peut servir à tout le monde je détail.
Alors je vais expliquer ce qu'est un arbre binaire vite fait: c'est une structure où on a
des points. Un point s'appele un noeud. En fait, dans un noeud on met une valeur par
exemple. Un noeud possède un fils gauche et un fils droit: deux autres noeuds. On appele le
noeud d'origine le père ou bien parent. La racine c'est le noeud le plus haut. Les feuilles,
les plus bas.
Exemple d'arbres pas binaires: une arbrorescence de dossiers (les noeuds contiennent un
ensemble de fichiers, la racine, c'est le lecteur).
Bref, un tas, c'est un arbre qui peut s'écrire de gauche à droite. Regarde l'exemple ici:
http://brassens.upmf-grenoble.fr/IMSS/limass/algoprog/Tris/TriArbre1.gif
Tu vois, il est particuliers parce qu'en bas il est plat et le seul "vide" se trouve à
droite.
En fait ce qu'il y'a de bien dans cet arbre, c'est qu'il peut s'écrire sous forme de vecteur
directement (l'exemple correspond au vecteur ici:
http://brassens.upmf-grenoble.fr/IMSS/limass/algoprog/Tris/TriArbre.html)
Bon, après la théorie, l'algo.
La fonction la plus importante se nomme entasser():
pour un noeud donné, on garde dans max le plus grand de ses deux fils et de lui,
ensuite on échange la valeur du père avec celle du plus grand.
(exemple: pere=6, fils-g= 7, fils-d= 3 =>> pere= 7, fils-g= 6, fils-d= 3)
C'est tout !!! Pour cette fonction...
Ensuite, on va faire la première fonction, celle qui construit le tas à partir d'un vecteur.
Comme un tas peu s'écrire en vecteur, on peut trouver une formule qui est (indices de 0 à n):
pour un noeud à l'indice i, son fils gauche se trouve à l'indice 2i+1 et le droit 2i+2 (si tu regardes bien l'arbre de l'exemple et en réflechissant, c'est logique)
Donc son père en partie entière de: (i-1)/2.
Bref, la fonction construit commence au dernier noeud qui possède un fils ou des fils (donc en (n-1)/2 avec n indice du dernier elt du tableau).
Ensuite pour chaque noeud voisin vers la gauche (on decrémente la valeur précédente à chaque pas), on fait appel à entasser(ce_noeud).
Voila, reste plus qu'une fonction: celle qui sera appelée.
Du dernier noeud (n) au premier (0) on echange les valeurs de ce noeud et de la racine de l'arbre et ensuite (l'ordre est important) on entasse la racine de l'arbre.
Bref, l'ensemble de l'algo s'écrit en trois petites fonctions voire une de plus pour void echanger(int &a, int &b) {int temp= a; a= b; b) temp; } et elles font que quelques lignes chacunes.
En fait, le principe parait compliqué, mais une fois assimilé, c'est tout aussi simple qu'un tri par échange. Bon j'abuse un peu, mais franchement c'est pas difficile.
Enfin, voiçi une petite animation qui explique ce qui se passe. On a pas l'impression que ce truc est plus rapide que ton tri, mais il marche excessivement bien surtout si l'arbre est tri" complètement à l'envers. Le pire des cas est celui où il est déjà trié, alors là, c'est très lent par rapport à ton tri, mais en moyenne le temps est plus court.
ANIMATION: http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/heapsort.html
c'est du Java, elle est vraiment très bien faite, et y'en a pleins d'autres sur le site ;-)
Bon, voilà, j'espère que ca t'aura aidé toi et d'autres. Je dépose dans quelques instants un e source que j'ai faite sur le sujet.
19 avril 2004 à 20:50
19 avril 2004 à 13:00
while(1)
{
if(i + 1 == MAX) break;...
}
par
while(i + 1 != MAX)
{
...
}
19 avril 2004 à 12:58
Tu devrais aussi dire la complexité de ton algo pour voir s'il est interressant
19 avril 2004 à 11:23
J'ai fais comme toi (ie: commencer par implémenté celui çi) puis finalement, ayant entendu parlé du tris par tas, je l'ai fais, et crois moi si ca t'intérresse tu peux le faire, il est quasiement aussi simple, et c'est l'un des plus puissants.
Sinon pour le code quelques petites choses:
main renvoie obligatoirement un entier (c'est dans le standart), 0 signifie bein terminé, 1 mal terminé (sous la plupart des OS, mais unemacro se nomme EXIT_SUCCESS et une autre EXIT_FAILURE dans stdlib.h ou bien cstdlib si tu utilisesla STL)
#define, c'est une macro, pas une constante, on peux mettre const à la place, c'est pareil sauf que le compilateur réalisera un contrôle des types dans ce cas et pas dans celui du #define. C'est donc important.
cout << "\n" ; peut être remplacé par cout << endl; car le endl fait en plus un flush ce qui permet d'être sûr que le contenu du flot sera imprimé à l'écran (ou du moins au flot de sortie standart associé à cout). endl va à la ligne. Si tu veux être sur que ca écrive sans aller à la ligne, utilise cout << flush;
la combine finale du int debug peut être remplacée par un getch() défini dans conio.h pour DEV C++ sinon je ne sais pas. De plus cette fonction renvoie un code correspondant à la touche pressée.
Sinon j'aime bien l'implémentation des tris. La tienne est efficace même pour ce genre de tri. Bien programmé.
19 avril 2004 à 11:23
J'ai fais comme toi (ie: commencer par implémenté celui çi) puis finalement, ayant entendu parlé du tris par tas, je l'ai fais, et crois moi si ca t'intérresse tu peux le faire, il est quasiement aussi simple, et c'est l'un des plus puissants.
Sinon pour le code quelques petites choses:
main renvoie obligatoirement un entier (c'est dans le standart), 0 signifie bein terminé, 1 mal terminé (sous la plupart des OS, mais unemacro se nomme EXIT_SUCCESS et une autre EXIT_FAILURE dans stdlib.h ou bien cstdlib si tu utilisesla STL)
#define, c'est une macro, pas une constante, on peux mettre const à la place, c'est pareil sauf que le compilateur réalisera un contrôle des types dans ce cas et pas dans celui du #define. C'est donc important.
cout << "\n" ; peut être remplacé par cout << endl; car le endl fait en plus un flush ce qui permet d'être sûr que le contenu du flot sera imprimé à l'écran (ou du moins au flot de sortie standart associé à cout). endl va à la ligne. Si tu veux être sur que ca écrive sans aller à la ligne, utilise cout << flush;
la combine finale du int debug peut être remplacée par un getch() défini dans conio.h pour DEV C++ sinon je ne sais pas. De plus cette fonction renvoie un code correspondant à la touche pressée.
Sinon j'aime bien l'implémentation des tris. La tienne est efficace même pour ce genre de tri. Bien programmé.
19 avril 2004 à 07:35
Ceci mis à part, c'est tjs très bien de s'y essayer soi-même (ça c'est sûr et certain), mais si tu as besoin de ce genre de routine pour un programme qui aura réellement besoin d'être efficace (par exemple pour un jeu), je te conseil d'utiliser la STD et son en-tête . Il y a là dedans des algorithmes de tris et de manipulation écrits par Bjarne Stroustrup et des amis mathématiciens, je pense que ça vaut le coup de leur faire confiance point de vue optimisation ^^
j'ai pas du tt le temps mtnt, mais je te conseil d'essayer de trouver des infos là dessus ;-)
18 avril 2004 à 17:41
le void en parametre est reserver au prototype, donc pas la peine de le mettre pour main, et fait plutot int main()
18 avril 2004 à 15:52