π
<-
Chat plein-écran
[^]

Algorithme de tri en C

Discussions scientifiques et scolaires

Algorithme de tri en C

Message non lude MMBC » 17 Oct 2017, 15:54

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 !
ImageImage
Image
Avatar de l’utilisateur
MMBCModo
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 66.7%
 
Messages: 107
Images: 1
Inscription: 16 Mai 2017, 19:20
Genre: Femme
Calculatrice(s):
MyCalcs profile
Classe: Ex prof
YouTube: Eyone
Facebook: Emma Cadet

Re: Algorithme de tri en C

Message non lude Adriweb » 17 Oct 2017, 19:36

envoyé en mp :P
Image

MyCalcs: Help the community's calculator documentations by filling out your calculators info!
MyCalcs: Aidez la communauté à documenter les calculatrices en donnant des infos sur vos calculatrices !
Inspired-Lua.org: All about TI-Nspire Lua programming (tutorials, wiki/docs...)
Avatar de l’utilisateur
AdriwebAdmin
Niveau 16: CC2 (Commandeur des Calculatrices)
Niveau 16: CC2 (Commandeur des Calculatrices)
Prochain niv.: 80.1%
 
Messages: 14606
Images: 1216
Inscription: 01 Juin 2007, 00:00
Localisation: France
Genre: Homme
Calculatrice(s):
MyCalcs profile
Twitter/X: adriweb
GitHub: adriweb

Re: Algorithme de tri en C

Message non lude Lionel Debroux » 17 Oct 2017, 20:13

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.
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Avatar de l’utilisateur
Lionel DebrouxSuper Modo
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Prochain niv.: 11.2%
 
Messages: 6859
Inscription: 23 Déc 2009, 00:00
Localisation: France
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: -
GitHub: debrouxl

Re: Algorithme de tri en C

Message non lude clifward » 17 Oct 2017, 22:33

Et sinon, tu serais pas en train de faire les problèmes de prologin en ce moment ? :troll:
Image
Avatar de l’utilisateur
clifwardMembre UPECS
Niveau 16: CC2 (Commandeur des Calculatrices)
Niveau 16: CC2 (Commandeur des Calculatrices)
Prochain niv.: 26.4%
 
Messages: 593
Images: 6
Inscription: 20 Sep 2015, 17:50
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile
Classe: CentraleSupelec

Re: Algorithme de tri en C

Message non lude MMBC » 18 Oct 2017, 07:33

Lionel Debroux a écrit: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 a écrit:Et sinon, tu serais pas en train de faire les problèmes de prologin en ce moment ? :troll:

Absolument rien à voir :P
ImageImage
Image
Avatar de l’utilisateur
MMBCModo
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 66.7%
 
Messages: 107
Images: 1
Inscription: 16 Mai 2017, 19:20
Genre: Femme
Calculatrice(s):
MyCalcs profile
Classe: Ex prof
YouTube: Eyone
Facebook: Emma Cadet

Re: Algorithme de tri en C

Message non lude Adriweb » 18 Oct 2017, 12:31

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

MyCalcs: Help the community's calculator documentations by filling out your calculators info!
MyCalcs: Aidez la communauté à documenter les calculatrices en donnant des infos sur vos calculatrices !
Inspired-Lua.org: All about TI-Nspire Lua programming (tutorials, wiki/docs...)
Avatar de l’utilisateur
AdriwebAdmin
Niveau 16: CC2 (Commandeur des Calculatrices)
Niveau 16: CC2 (Commandeur des Calculatrices)
Prochain niv.: 80.1%
 
Messages: 14606
Images: 1216
Inscription: 01 Juin 2007, 00:00
Localisation: France
Genre: Homme
Calculatrice(s):
MyCalcs profile
Twitter/X: adriweb
GitHub: adriweb

Re: Algorithme de tri en C

Message non lude MMBC » 18 Oct 2017, 13:17

C'est du C89, C99 ou C11 ?
ImageImage
Image
Avatar de l’utilisateur
MMBCModo
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 66.7%
 
Messages: 107
Images: 1
Inscription: 16 Mai 2017, 19:20
Genre: Femme
Calculatrice(s):
MyCalcs profile
Classe: Ex prof
YouTube: Eyone
Facebook: Emma Cadet

Re: Algorithme de tri en C

Message non lude clifward » 18 Oct 2017, 18:45

On peut voir le code, pour comprendre le troll ? :P
Image
Avatar de l’utilisateur
clifwardMembre UPECS
Niveau 16: CC2 (Commandeur des Calculatrices)
Niveau 16: CC2 (Commandeur des Calculatrices)
Prochain niv.: 26.4%
 
Messages: 593
Images: 6
Inscription: 20 Sep 2015, 17:50
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile
Classe: CentraleSupelec

Re: Algorithme de tri en C

Message non lude Lionel Debroux » 18 Oct 2017, 18:54

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 :)
Membre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Avatar de l’utilisateur
Lionel DebrouxSuper Modo
Niveau 14: CI (Calculateur de l'Infini)
Niveau 14: CI (Calculateur de l'Infini)
Prochain niv.: 11.2%
 
Messages: 6859
Inscription: 23 Déc 2009, 00:00
Localisation: France
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: -
GitHub: debrouxl

Re: Algorithme de tri en C

Message non lude chadok » 20 Oct 2017, 21:31

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:
Avatar de l’utilisateur
chadok
Niveau 8: ER (Espèce Rare: nerd)
Niveau 8: ER (Espèce Rare: nerd)
Prochain niv.: 32%
 
Messages: 88
Inscription: 10 Nov 2013, 16:03
Localisation: Bretagne
Genre: Homme
Calculatrice(s):
MyCalcs profile

Suivante

Retourner vers Maths, physique, informatique et autre...

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 14 invités

-
Rechercher
-
Social TI-Planet
-
Sujets à la une
Comparaisons des meilleurs prix pour acheter sa calculatrice !
Aidez la communauté à documenter les révisions matérielles en listant vos calculatrices graphiques !
Phi NumWorks jailbreak
123
-
Faire un don / Premium
Pour plus de concours, de lots, de tests, nous aider à payer le serveur et les domaines...
Faire un don
Découvrez les avantages d'un compte donateur !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partenaires et pub
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
1122 utilisateurs:
>1103 invités
>14 membres
>5 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Autres sites intéressants
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)