EFFECTUER UN TRI DE VALEURS ENTIÈRES (DEV-C++4.1)

Signaler
Messages postés
37
Date d'inscription
jeudi 15 janvier 2004
Statut
Membre
Dernière intervention
22 octobre 2004
-
cs_djl
Messages postés
3011
Date d'inscription
jeudi 26 septembre 2002
Statut
Membre
Dernière intervention
27 novembre 2004
-
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

cs_djl
Messages postés
3011
Date d'inscription
jeudi 26 septembre 2002
Statut
Membre
Dernière intervention
27 novembre 2004
7
ben si?

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++
TeLeTUbIz
Messages postés
215
Date d'inscription
mercredi 30 juillet 2003
Statut
Membre
Dernière intervention
25 septembre 2010

... et C et C++ sont incompatibles !
cs_djl
Messages postés
3011
Date d'inscription
jeudi 26 septembre 2002
Statut
Membre
Dernière intervention
27 novembre 2004
7
Mat06 ==> justement c'est pas le moment de prendre des mauvaise habitude

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++)
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

you are ment to evolve ;-)
cs_Mat06
Messages postés
37
Date d'inscription
jeudi 15 janvier 2004
Statut
Membre
Dernière intervention
22 octobre 2004

Pour mon niveau on s'en fiche royalement !!
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

non on ne s'en fiche pas. les standards ne sont pas les mêmes, et les spectres d'utilisation non plus.
cs_Mat06
Messages postés
37
Date d'inscription
jeudi 15 janvier 2004
Statut
Membre
Dernière intervention
22 octobre 2004

On s'n fout un peu de savoir si c'est du C++ ou du C !! NAN ??
cs_djl
Messages postés
3011
Date d'inscription
jeudi 26 septembre 2002
Statut
Membre
Dernière intervention
27 novembre 2004
7
ben oui parce que getch c'est pour la saisie (en passant, getch c'est pas vraiment standard ;), encore moin c++ )
TeLeTUbIz
Messages postés
215
Date d'inscription
mercredi 30 juillet 2003
Statut
Membre
Dernière intervention
25 septembre 2010

ouai, c'est devenu un forum sur les standarts et les tris :-)
TeLeTUbIz
Messages postés
215
Date d'inscription
mercredi 30 juillet 2003
Statut
Membre
Dernière intervention
25 septembre 2010

ouai, le endl je susi d'accord, mais je susi un peu chiant parce que lorsque l'on fait un truc du genre:
cout << "bonjour";
while(1)
{
calcul_quelconque();
getch();
}

ce genre de truc, il arrive que bonjour ne s'affiche pas.
cs_Mat06
Messages postés
37
Date d'inscription
jeudi 15 janvier 2004
Statut
Membre
Dernière intervention
22 octobre 2004

Apparement, mon source est devenu un forum !! lol
cs_djl
Messages postés
3011
Date d'inscription
jeudi 26 septembre 2002
Statut
Membre
Dernière intervention
27 novembre 2004
7
TeLeTUbIz ==> oui pour le endl, mais reelement necessaire seulement avant de faire un cin, mettre systemetiquement endl pour terminer une ligne est inutile

sinon le return 0 n'est pas obligatoire en c++, mais bon, ca depend malheuresement encore des compilos
TeLeTUbIz
Messages postés
215
Date d'inscription
mercredi 30 juillet 2003
Statut
Membre
Dernière intervention
25 septembre 2010

Voila, un tas est un arbre binaire particulier.
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.
Pamaury
Messages postés
341
Date d'inscription
jeudi 3 avril 2003
Statut
Membre
Dernière intervention
17 juin 2008
2
Tu pourrais me donner des infos sur le tri par tas s'il te plait .
vecchio56
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7
et puis tu pourrais remplacer
while(1)
{
if(i + 1 == MAX) break;...
}

par
while(i + 1 != MAX)
{
...
}
vecchio56
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7
Le problème c'est que ton algo n'est pas du tout réutilisable, il utilise des variables globales. Ce serait préférable de fournir une fonction qui prend par exemple en paramètre un tableau et sa taille.
Tu devrais aussi dire la complexité de ton algo pour voir s'il est interressant
TeLeTUbIz
Messages postés
215
Date d'inscription
mercredi 30 juillet 2003
Statut
Membre
Dernière intervention
25 septembre 2010

C'est un tri par échange. Il est très basique mais rapide à implémenté, alors ca fait son charme. Je l'aime bien; mais il a une complexité de l'ordre de n² alors qu'un tri par tas a une complexité moyenne de l'ordre de n.ln(n)
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é.
TeLeTUbIz
Messages postés
215
Date d'inscription
mercredi 30 juillet 2003
Statut
Membre
Dernière intervention
25 septembre 2010

C'est un tri par échange. Il est très basique mais rapide à implémenté, alors ca fait son charme. Je l'aime bien; mais il a une complexité de l'ordre de n² alors qu'un tri par tas a une complexité moyenne de l'ordre de n.ln(n)
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é.
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008

Si tu postes un algo, l'essentiel c'est plutôt qu'il soit bon, pas qu'il marche, ça ça va de soi ^^
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 ;-)
cs_djl
Messages postés
3011
Date d'inscription
jeudi 26 septembre 2002
Statut
Membre
Dernière intervention
27 novembre 2004
7
je connais pas les differents algo de tri, mais pour un debut c'est pas mal

le void en parametre est reserver au prototype, donc pas la peine de le mettre pour main, et fait plutot int main()
cs_Mat06
Messages postés
37
Date d'inscription
jeudi 15 janvier 2004
Statut
Membre
Dernière intervention
22 octobre 2004

N'hésitez pas a commenter !