Page 1 of 2

Algorithme de tri en C

Unread postPosted: 17 Oct 2017, 15:54
by MMBC
Bonjour et bienvenue dans ce mini concours.


C'est très simple : vous avez un tableau de float, de taille t. Vous devez écrire en C un programme qui trie le tableau dans l'ordre décroissant.
Plus votre programme sera rapide, mieux vous serez classé ;)
Pour participer, il suffit simplement de m'envoyer le code source par message privé avec pour objet "algo tri".
Vous devez aussi préciser qui vous a aidé (si quelqu'un vous a aidé).
Je testerai vos programmes moi même.

A vos claviers, prêts ? Codez !

Re: Algorithme de tri en C

Unread postPosted: 17 Oct 2017, 19:36
by Adriweb
envoyé en mp :P

Re: Algorithme de tri en C

Unread postPosted: 17 Oct 2017, 20:13
by Lionel Debroux
Deux questions qui peuvent être utiles à ceux qui veulent participer, et des remarques:
  • A quel dialecte de C et quelles contraintes de portabilité le code source doit-il se conformer ? Par exemple, si un vilain ou une vilaine s'amuse à écrire du C11 en utilisant des builtins GCC / Clang pour optimiser, ça peut être du C, sans convenir à ton environnement de test :)
  • jusqu'à quel ordre de grandeur prévois-tu de monter la valeur du nombre d'éléments t ? 2^30 (~10^9) floats sont triables en mémoire sur la plupart des PCs x86_64 récents, mais 2^32 floats = 16 GB sur la plupart des architectures sont déjà beaucoup moins accessibles. Et les algorithmes les plus efficaces pour pouvoir trier 2^30 éléments ne sont pas les mêmes que pour trier 2^7 éléments, ou pour trier 2^34 éléments sur un ordinateur qui ne dispose pas de tant de RAM.

Une fois que les algos (puisqu'il faut probablement une fonction de tri efficace sur une large gamme de tailles) sont choisis, c'est la qualité de l'implémentation, et dans une moindre mesure le niveau d'optimisation lors de la génération de code, qui feront la différence.

Re: Algorithme de tri en C

Unread postPosted: 17 Oct 2017, 22:33
by clifward
Et sinon, tu serais pas en train de faire les problèmes de prologin en ce moment ? :troll:

Re: Algorithme de tri en C

Unread postPosted: 18 Oct 2017, 07:33
by MMBC
Lionel Debroux wrote:Deux questions qui peuvent être utiles à ceux qui veulent participer, et des remarques:
  • A quel dialecte de C et quelles contraintes de portabilité le code source doit-il se conformer ? Par exemple, si un vilain ou une vilaine s'amuse à écrire du C11 en utilisant des builtins GCC / Clang pour optimiser, ça peut être du C, sans convenir à ton environnement de test :)
  • jusqu'à quel ordre de grandeur prévois-tu de monter la valeur du nombre d'éléments t ? 2^30 (~10^9) floats sont triables en mémoire sur la plupart des PCs x86_64 récents, mais 2^32 floats = 16 GB sur la plupart des architectures sont déjà beaucoup moins accessibles. Et les algorithmes les plus efficaces pour pouvoir trier 2^30 éléments ne sont pas les mêmes que pour trier 2^7 éléments, ou pour trier 2^34 éléments sur un ordinateur qui ne dispose pas de tant de RAM.

Une fois que les algos (puisqu'il faut probablement une fonction de tri efficace sur une large gamme de tailles) sont choisis, c'est la qualité de l'implémentation, et dans une moindre mesure le niveau d'optimisation lors de la génération de code, qui feront la différence.


Que ce soit du C11 ou de l'ANSI, aucun problème, et je compile avec mingw-gcc (j'ai que ça sous la main).
Pour le nombre de valeurs, je ne dépasserai surement jamais la dizaine de millions.

Clifward wrote:Et sinon, tu serais pas en train de faire les problèmes de prologin en ce moment ? :troll:

Absolument rien à voir :P

Re: Algorithme de tri en C

Unread postPosted: 18 Oct 2017, 12:31
by Adriweb
Pour information, ma participation n'est probablement pas la plus rapide, mais est plutôt un troll, vous verrez pourquoi :troll:

Re: Algorithme de tri en C

Unread postPosted: 18 Oct 2017, 13:17
by MMBC
C'est du C89, C99 ou C11 ?

Re: Algorithme de tri en C

Unread postPosted: 18 Oct 2017, 18:45
by clifward
On peut voir le code, pour comprendre le troll ? :P

Re: Algorithme de tri en C

Unread postPosted: 18 Oct 2017, 18:54
by Lionel Debroux
Disons qu'il n'est pas allé chercher très loin la fonction de tri, et que si quelqu'un fait quelque chose de moins rapide, il lui est impossible de gagner :)

Re: Algorithme de tri en C

Unread postPosted: 20 Oct 2017, 21:31
by chadok
Ce site est sympa, il permet de visualiser les performances des différents algorithmes, en cliquant sur "Lancer les tris" :
http://lwh.free.fr/pages/algo/tri/tri.htm
Et en prime, le code de chaque méthode est donné :bj: