Algorithme de tri en C

[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 !

[Adriweb]

envoyé en mp

[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.

[clifward]

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

[MMBC]

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.

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

Absolument rien à voir

[Adriweb]

Pour information, ma participation n'est probablement pas la plus rapide, mais est plutôt un troll, vous verrez pourquoi

[MMBC]

C'est du C89, C99 ou C11 ?

[clifward]

On peut voir le code, pour comprendre le troll ?

[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

[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é