... et si les éléments à trier sont dans un vecteur, Il n'y a qu'à appeler la fonction qsort() qui est standard et se trouve dans le stdlib.h
Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Si vous programmez en C
... et si les éléments à trier sont dans un vecteur, Il n'y a qu'à appeler la fonction qsort() qui est standard et se trouve dans le stdlib.h
Si vous programmez en Haskell...
Et qu'on vous décrit le quicksort, vous écrivez :
Et t=1min...
Code : Sélectionner tout - Visualiser dans une fenêtre à part
2
Et vous passez à la suite !
--
Jedaï
Excellente discussion où on rend hommage à Sedgewick qui au passage après Fortan et C en est à "Algorithmes en C++".
J'aime bien Sedgewick pour le contenu, pour le style et pour les choix. Admirable Robert qui choisit UN LANGAGE et QUI NE S'Y TIENT PAS !!!!
Bravo à Ol9245 et à Souviron qui assènent quelques bonnes vérités qui vont sans dire et encore mieux en le disant.
Ce qu'on trouve est plus important que ce qu'on cherche.
Maths de base pour les nuls (et les autres...)
Je reviens y mettre mon grain de sel
Bon, en fait, tout dépend de ce que l'on a à trier...
Si vous avez tout au plus une centaines d'éléments (voir un millier) à trier, ce n'est pas la peine de se faire suer à implémenter un quicksort : franchement quel est l'intérêt d'avoir un temps de traitement de 20 milli-secondes plutôt qu'un traitement qui prendrait au plus 40 milli-secondes si c'est pour compléxifier le code inutilement et se prendre la tête à se souvenir de comment l'implémenter. ça, ça s'appelle de la masturbation intellectuelle.
Après, pour de lourds traitements, c'est clair, le quicksort fait la différence...
Bref, ça dépend donc aussi du contexte.
Bidouilleuse Delphi
Oui c'est certain, le contexte est prépondérant...
Entre un milliard de donnée, et un tableau d'une dizaine d'élément il y a un fossé.
Et je ne parle pas du cas particulier du tableau à 0 ou 1 élement, ou l'algorithme devient vide.
Implémentation Quicksort
Le principe général du Quicksort est en effet assez simple à retenir, mais la plupart des implémentations que l'on trouve sur le net provoque un stack overflow si on tri un tableau de 500 000 éléments qui contient seulement une dizaine de valeurs différentes. Faites l'essai, vous verrez !
Il faut alors mettre les mains dans le cambui, et si on n'est pas habitué, on n'y arrive pas ou au mieux on génére une usine à gaz dont on ne sait même pas si elle prévoit tous les cas.
Pour moi, la culture générale ne suffit pas : c'est comme si on essayait d'apprendre la mécanique uniquement avec des livres.
Je pense que les deux sont aussi important l'un que l'autre. Les solutions que l'on trouve sur le net ou qu'on lit, ne sont pas toujours adaptées exactement à nos problèmes. Il faut alors les adapter (enlevés ce qui ne sert à rien, ajouter d'autres contraintes,...). Et plus on s'est déjà cassé la tête sur des algorithmes (compréhension, optimisation, ...), plus on aura des facilités pour adapter la solution trouvée à notre problème.
C'est comme beaucoup de chose, il faut trouver le juste milieux.
Absolument, mais personne n'a dit que le net était la source pour trouver des SOURCES des algorithmes peformants !!Envoyé par nimzo78
De la doc oui, mais des sources d'algo, il y a peu d'endroits fiables (Graphics Gems, FAQ de comp.graphics.algorithms, etc..) de PROFESSIONNELS..
"Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".
Consultant indépendant.
Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
C, Fortran, XWindow/Motif, Java
Je ne réponds pas aux MP techniques
Ca c'est bien vrai !
Partons à sa recherche avec un exemple concret :
imaginons que tu veuille recruter un mec pour ce projet. C'est un bon exemple car d'un côté, tu as besoin d'un mec habile qui va te cracher du code tout de suite, d'un autre côté tu veux quand même pas un bourin qui a le nez dans le guidon. Si tu tombais sur le bon candidat, il pourrait évoluer dans la boite et y apporter du sang neuf.
A l'entretien d'embauche, tu poses la question du quicksort qui explose : comment le résoudre ?
le premier candidat te dit : "je réécrit le quicksort dans une version non récursive et ça marchera.
le deuxième candidat te dit : "500000 nombres qui ne prennent que 10 valeurs ? je suis pas sur que le quicksort soit l'algo idéal. je vais chercher un algo mieux adapté.
Lequel de ces deux vas-tu recruter ?
"La vraie grandeur se mesure par la liberté que vous donnez aux autres, et non par votre capacité à les contraindre de faire ce que vous voulez." Larry Wall, concepteur de Perl.
J'aimerai un candidat ni trop généraliste, ni trop bourrin. La deuxième me satisferai mieux que la première, mais je serai content d'avoir déjà la première. Je recrute actuellement un développeur c# en cdi (l'annonce est sur ce site "TNS dotnet"), et j'ai déjà reçu quelques candidats. Aucun n'a pu me décrire même de façon globale un algorithme de tri autre que le tri bulle. C'était tous des ingénieurs. Ils les ont surement vu en cours ou dans des livres. Mais (surement) comme ils ne les ont pas essayé eux mêmes, ils ont oublié comment ils fonctionnaient.
Pour ma part, si le nombre d'éléments différents du tableau n'est pas trop grand, j'utiliserai un tableau de compteurs ou chaque indice correspondrait à une valeur (avec une table de correspondance créée dynamiquement), puis je compterai le nombre d'occurence de chaque valeurs différentes du tableau, pour les réécrire bêtement ensuite dans le tableau (dans l'ordre bien sur). Je lis une fois chaque valeur et j'écris une fois chaque valeur, avec seulement un petit travail de préparation, et un petit tri par insertion des quelques valeurs différentes du tableau pour les réécrire dans l'ordre.
Il y a surement d'autres solutions adaptées à ce cas de figure.
Mais on cherche souvent à avoir un algo de tri performant (sans être forcément le meilleurs dans tous les cas) dont tout le monde pourrait se servir, et surtout qui ne plante pas dans certaines conditions.
Voilà qui est ... terrifiant ! L'idée que des types incapables de retrouver sur le moment l'idée du tri par sélection ou par insertion (sachant de plus qu'ils les ont forcément vu en cours d'algo) sont ingénieurs informatiques et concoctent des logiciels me glace les sangs !Je recrute actuellement un développeur c# en cdi (l'annonce est sur ce site "TNS dotnet"), et j'ai déjà reçu quelques candidats. Aucun n'a pu me décrire même de façon globale un algorithme de tri autre que le tri bulle. C'était tous des ingénieurs. Ils les ont surement vu en cours ou dans des livres. Mais (surement) comme ils ne les ont pas essayé eux mêmes
--
Jedaï
Tout dépend de ta définition d'ingenieur...Voilà qui est ... terrifiant ! L'idée que des types incapables de retrouver sur le moment l'idée du tri par sélection ou par insertion (sachant de plus qu'ils les ont forcément vu en cours d'algo) sont ingénieurs informatiques et concoctent des logiciels me glace les sangs !
--
Jedaï
Perso, ca ne me dérange pas qu'un ingenieur ne connaisse pas une réponse, tant qu'il sait où la chercher en cas de besoin.
Je préfère quelqu'un qui sait résoudre des problèmes, plutot que quelqu'un qui connait des solutions.
Signé: un ingenieur (
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Tu n'as pas bien lu ma réponse : mon problème n'est pas que l'ingénieur ne connaisse que le tri-bulle, mon problème est qu'il n'est pas capable de penser à des idées aussi basiques que le tri par insertion ou le tri par sélection... Pas parce que je pense que connaître ces tris a la moindre importance pour un ingénieur (de toute façon il est bien rare de les utiliser dans le monde réel), mais parce que si l'ingénieur n'a pas le minimum d'imagination et/ou de bon sens requis pour retrouver ces méthodes (de tête, pas avec Google), je ne peux pas croire qu'il fera un bon boulot par la suite, aurait-il la meilleure bibliothèque d'algorithme du monde à sa disposition : il trouvera moyen de faire des trucs inutiles/stupides qui fera perdre tout le bénéfice de ces algos.
Confierais tu vraiment un programme d'une quelconque importance à un zozo qui ne sait classer ses cartes qu'en les intervertissant deux à deux jusqu'à ce qu'elles soient dans l'ordre ?
--
Jedaï
bah je suis d'accord avec pseudocode et te trouve un peu.. borné (scuze moi, pas de jeu de mots mathématiques hein
Comme disait pseudocode, le but est que quelqu'un qui est face à un problème sache OU chercher, et comprenne ce qu'il trouve.
Comme disait Pascal "une tête bien faite vaut mieux qu'une tête bien pleine"...
Et je dois dire que je mépriserais la personne qui me demanderait ce genre de trucs en entretien, et je me casserais bien content de ne pas entrer dans cette boîte....
Et en ce qui concerne les tris, je n'en ai jamais appris aucun.. Mais quand j'en ai eu besoin, j'ai regardé d'abord dans les man pages, où j'ai trouvé qsort, et dans le man j'ai vu que c'était quicksort. OK j'ai pas été plus loin.
Et puis après pour autre chose j'ai eu besoin d'aller fouiller dans le Sedgewick. Et je suis tombé sur l'algo de quicksort, du coup j'ai regardé en 5 min. Et j'ai vu que c'était rusé, mais je n'ai pas voulu rentrer dedans.. ça marche, il y a une fonction toute faite qui fait ça, j'ai d'autres problèmes à résoudre que de réinventer ce que quelqu'un a mis des années à trouver, donc ciao basta ça me suffit. ça existe et ça marche . Point final.
Mon boulot est de résoudre des problèmes NON ENCORE résolus, pas de re-tenter de résoudre des problèmes résolus...
"Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".
Consultant indépendant.
Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
C, Fortran, XWindow/Motif, Java
Je ne réponds pas aux MP techniques
"La vraie grandeur se mesure par la liberté que vous donnez aux autres, et non par votre capacité à les contraindre de faire ce que vous voulez." Larry Wall, concepteur de Perl.
Borné (en passant je trouve le terme très insultant) ? Parce que j'aimerais bien qu'un ingénieur en informatique soit capable de trouver d'autre algorithmes de tri que le tri à bulle à froid ? Je ne demande pas qu'il se souvienne de "noms", ni même qu'il soit capable de réécrire l'algorithme sans bugs et précisément, simplement qu'il soit suffisamment éveillé pour imaginer une méthode de tri aussi simple et intuitive que le tri par sélection, ou le tri par insertion...bah je suis d'accord avec pseudocode et te trouve un peu.. borné (
Ben c'est exactement ce que j'attends d'un ingénieur : une tête bien faite. Parce que pour trouver des algorithmes c'est aussi simple que de faire une recherche dans Google, mais après faut être capable de les comprendre et de les appliquer à bon escient, et ça, ça me semble demander un tout petit peu de sens de l'informatique tout de même.Comme disait Pascal "une tête bien faite vaut mieux qu'une tête bien pleine"...
--
Jedaï
Avis personnel: ca n'a rien a voir avec l'ingénierie . Tu peux remplacer dans ta phrase les mots "ingénieur en informatique" par "mathématicien", ou "éleve de terminale" ou même "être humain".Parce que j'aimerais bien qu'un ingénieur en informatique soit capable de trouver d'autre algorithmes de tri que le tri à bulle à froid ? Je ne demande pas qu'il se souvienne de "noms", ni même qu'il soit capable de réécrire l'algorithme sans bugs et précisément, simplement qu'il soit suffisamment éveillé pour imaginer une méthode de tri aussi simple et intuitive que le tri par sélection, ou le tri par insertion...
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
C'est pas faux, même si je ne demanderais sûrement pas à un élève de terminale complètement à froid, de préférence je lui donnerai un paquet de carte, je lui demanderais de le trier et finalement je lui demanderais de me décrire comment il fait. Presque à coup sûr il aura utilisé un tri par insertion (à peu près), à mon avis c'est le tri le plus naturel avec un paquet de carte. D'ailleurs un ingénieur qui sait décrire le tri à bulle (pas naturel du tout !) et pas un tri par insertion, c'est un ingénieur qui a la tête pleine mais pas assez (et de trucs inutiles en plus) mais pas bien faite je pense.
--
Jedaï
Milles excuses mais sur le coup je ne trouvais pas de mots équivalent à ce que j'avais en tête (limites mathématiques ; ensemble fini ; ensemble b...). Donc comme je disais aucune intention malveillante là-dedans...
Désolé..
Là nous sommes d'accord, mais si tu reprends ton post initial sur le sujet, tu verras que ce que tu demandais c'était qu'il te sorte le tri à bulle ou le tri par insertion...
Et je RE-dis que je m'en fous comme de l'an 40.. (je n'ai d'ailleurs aucune idée de ce que c'est, ni l'un ni l'autre)...
"Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".
Consultant indépendant.
Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
C, Fortran, XWindow/Motif, Java
Je ne réponds pas aux MP techniques
Peut-être que tu devrais lire attentivement avant de critiquer :
puis :Voilà qui est ... terrifiant ! L'idée que des types incapables de retrouver sur le moment l'idée du tri par sélection ou par insertion (sachant de plus qu'ils les ont forcément vu en cours d'algo) sont ingénieurs informatiques et concoctent des logiciels me glace les sangs !
Où est-ce que je demande qu'il me ressorte le nom ou l'algo précis du tri ?mon problème n'est pas que l'ingénieur ne connaisse que le tri-bulle, mon problème est qu'il n'est pas capable de penser à des idées aussi basiques que le tri par insertion ou le tri par sélection...
--
Jedaï
du sang, du sang, du sang...
ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager