C Structure de données et algorithme de tri.

Bonjour,

j’écris ce sujet car je vais me remettre au C avec votre tuto et le livre K&R 2e mais n’étant pas dans une formation ou je fais beaucoup de dev je n’ai pas eu beaucoup de cours d’algorithme c’est pourquoi j’aimerais savoir selon vous quelless sont les structure de données et algo de tri que tout développeur qui se respecte doit connaître ?

+Selon vous quels sont les sujets d’algo importants à connaître ? je pense notamment à la complexité algorithmique, est-ce indispensable ?
Voilà si vous avez des conseils, des bouquins ou tutoriel à proposer je suis également preneur! Merci d’avance !

Hello,

La complexité algorithmique est importante. C’est ce qui permettra de jaugé la performance de tes algos. Ici tu as la liste de différents tris. Je pense qu’il est important de les connaitre tous un peu, au moins pour la culture. Sinon pour ma part je pense que le tri rapide doit être étudié

Voici 2 vidéos que je trouve assez amusantes sur les tris ! (Penser à couper le son !)

• https://www.youtube.com/watch?v=BeoCbJPuvSE
• https://www.youtube.com/watch?v=kPRA0W1kECg

Perso mon préféré est le tri fusion que je trouve très fun à coder =)

Salut,

Le forum de Prologin (un concours de problem solving français) possède ces deux sujets qui pourraient t’intéresser : les algorithmes et structures de données à connaître et des ressources concernant l’algorithmique.

Merci à vous deux !

Lu’!

Moui, mais non. Elle va te permettre d’évaluer (à la louche hyper large) comment vont évoluer les performances en fonction de la taille du problème. La vraie évaluation, c’est par mesure sur des instances réalistes, parce que les mécanismes de caches et la manière d’accéder à la mémoire ont un impact bien plus énorme sur les performances.

Je ne suis pas du tout convaincu de la pertinence de savoir implémenter des algos de tri courants. Il y a presque aucune chance que tu doives le faire dans une vraie situation sans avoir accès aux ressources nécessaires.

Il vaut en revanche la peine de jeter un oeil aux caractéristiques des 3-4 algos de tri les plus communs, ça oui. Mais le plus important, pour répondre à ta question plus générale, c’est à mon avis d’apprendre à reconnaitre les cas d’usages courants d’un bon nombre d’algos et de structures de données. Donc de les connaitre superficiellement, mais de savoir à quoi ils servent, quand ils peuvent être utiles.

Je préfère mille fois aller chercher sur Internet comment implémenter ou trouver une implémentation existante d’un bloom filter ou d’un B+ tree que de savoir les implémenter de tête ou d’en connaitre les caractéristiques exactes. Le plus important dans mon travail étant de savoir qu’ils existent, et dans des situations précises savoir quelles sont les options à évaluer.

@victor : Je suis tout à fait d’accord avec toi sur le fond, mais il me semble que se frotter par soi même à ce genre de problématique est formateur. Cela de permet de mieux comprendre les problématiques en jeu, et tu comprendra mieux de quoi il s’agit lorsqu’on te parlera de ces choses là ensuite.

S’y frotter oui, en retenir l’implémentation plutôt que l’intuition et l’utilité, non.

Ce n’est que mon avis évidemment.