Discussion :

[Pacma]

Bonjour !

J'ai juste une question toute simple, est-ce que vous connaissez "par coeur" les tris classiques comme le tri par insertion, le tri par pivot, ... ?

Parce que lorsque j'en ai besoin, je fais une recherche rapide mais je ne les connais pas par coeur.

Merci bien !

[Trademark]

Je pense que la plupart des gens peuvent te les coder en relisant leur description et que la plupart les ont codé dans leur vie et connaissent leurs caractéristiques (complexité spatiale et temporelle). En tout cas il me faudrait un peu du temps pour en coder un de nul part...

Aussi, personne ne les "recodent" pas car on utilise ceux déjà disponibles dans les librairies du langage. Et si on a à les recoder c'est certainement pas aussi simple qu'un tri bateau.

[CodeurPlusPlus]

Il suffit de retrouver le principe de l'algo (de mémoire ou par une recherche). Ensuite on gribouille et on réfléchit pour trouver l'algo exact et sa complexité, puis on peut ensuite en faire une implémentation correcte. Les apprendre par coeur n'aurait aucun sens, dans ce cas il y aurait des centaines d'algorithmes (pas seulement de tri) à connaître par coeur.

[zaza576]

J'avais un enseignant qui me disait " Fais un dessin, tu verras ca ira mieux après..."

Si tu maîtrises bien un algorithme, tu peux le connaître par coeur.
Si tu doutes, poses ton algorithme sur le papier quitte à le dessiner si tu peux et essaies de parcourir tous les cas de figure. Une fois ceci fait, tu le codes.

On n'est pas non plus des compilateurs ! On est humain à la base. Pourquoi tout vouloir apprendre par coeur ?

[ol9245]

je connais le principe de plusieurs d'entre eux. Je pourrais les coder si j'avais du temps à perdre. Je ne les coderai jamais dans la vraie vie pk coder c'est sympa, mais débugguer c'est beurk. et puis tous les langages ou presque ont une fonction sort. ceci dit c'est très très très utile de connaître les principes généraux d'un maximum d'algorithmes usuels. Les algorithmes, c'est la géographie de l'informatique. Ils permettent de savoir où on est et de se diriger vers là ou on veut aller.

[zaza576]

Hello,

après c'est toujours intéressant, comme le disait le capitaine Haddock (ol9245), de connaître le contexte d'utilisation de ces algorithmes de tri et leur complexité.

Quand tu auras à traiter des flots de données de plusieurs Gigaoctets et que tu devras trier cela, en fonction du type de données, et du type d'algorithme utilisé pour trier, le temps de calcul ne sera pas le même, ni la consommation mémoire et CPU.

A chaque algorithme son problème. Eviter au maximum le O(n²) et O(e^n) ^^ !

[betaplus]

A mon sens, je ne vois pas l'intérêt d'apprendre des choses par coeur si elles ne représentent pas la base de ce dont tu as besoin. Il me semble en revanche essentiel de savoir rechercher de l'information et de l'évaluer.

Je trouve qu'il est important de pouvoir comprendre comment fonctionne différents algorithmes et d'en comprendre leurs avantages et leurs faiblesses. Et puis avec la pratique il y a des choses qui rentrent toutes seules.

Pour résumer, je trouve qu'il est plus important de comprendre que de savoir, même si parfois, pour comprendre il faut savoir au moins un minimum...

[anapurna]

salut
il est quand même intéressant de connaitre les différent algorithme
d'en connaitre l'utilité et ses contraintes.
je ne dis pas de connaitre son implémentation ... elle est pour ainsi dire déjà implémenté de nombreuses fois dans diverses librairies
mais connaitre le principe générale permet déjà d'affiné ta recherche d'optimisation.

un exemple me viens en tête qui connais le "Tri comptage" ?
très peu usité car de nombreuses contraintes mais si toutes les contrainte sont respecté il fait partie des trie les plus rapide.

comme le disait un des interlocuteur tout dépend du contexte


PS : Pour les Gigaoctets évite le "Tri comptage"

[zaza576]

un exemple me viens en tête qui connais le "Tri comptage" ?
très peu usité car de nombreuses contraintes mais si toutes les contrainte sont respecté il fait partie des trie les plus rapide.

Je découvre cet algo de tri "comptage". Est-il plus rapide que le quicksort ou le tri bucket ?

Qu'utiliserais-tu pour trier de très gros volumes de données (de l'ordre du Go, pas forcément un filesystem avec plusieurs fichiers de Go mais aussi des milliards de petits fichiers) par contrainte ?

[anapurna]

salut

dans certaine condition il peut être plus rapide que le quicksort puisqu'il ne se fait quand une passe
Je ne compte pas l'initialisation du tableau receveur
ni la remise en ordre des valeurs du tableau dans le tableau d'origine

Par contre pour de Go ne même pas penser a ce type d'algo trop de variables et l'etendu est trop importante

Ce que dit wikipédia sur le sujet des tri

Tris par comparaison
Algorithmes lents

Ces algorithmes sont lents pour plus de 20 éléments parce qu'ils sont en O(n2).

Tri à bulles : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, stable et en place ; amusant mais pas efficace
Tri par sélection : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, pas stable si tri sur place ; rapide lorsque l'on a moins de 7 éléments
Tri par insertion : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, stable et en place. C'est le plus rapide et le plus utilisé pour des listes de moins de 15 éléments ;

Algorithmes plus rapides

Tri de Shell (shell sort) : Amélioration du tri par insertion, mais pas stable. Complexité : au pire O(n \log^2 n) pour la série de pas 2^p3^q et O(n\sqrt{n}) pour la série de pas 2^k-1. On ne connaît pas de série donnant O(n \log n).

Tri fusion (merge sort) : O(n \log n) en moyenne et dans le pire des cas, stable mais pas en place3 ;
Tri rapide (quick sort) : O(n \log n) en moyenne, mais en O(n^2) (quadratique) au pire cas4, en place mais pas stable
Introsort : Amélioration du tri rapide, qui permet une exécution en O(n \log n) dans tous les cas.

Tri par tas (heap sort) : O(n \log n) en moyenne et dans le pire des cas, en place mais pas stable. Toujours environ deux fois plus lent que le tri rapide, c'est-à-dire aux alentours de O(n \log n), il est donc intéressant de l'utiliser si l'on soupçonne que les données à trier seront souvent des cas quadratiques pour le tri rapide ;

Tri par ABR : O(n \log n) en moyenne, O(n^2) dans le pire des cas. Ce tri est un des plus lents (parmi les tris rapides) et des plus gourmands en mémoire à cause de la structure d'arbre binaire à manipuler. Il est possible de le rendre O(n \log n) dans tous les cas en maintenant un arbre équilibré (Arbre AVL).

Smoothsort : tri inspiré du tri par tas en utilisant un arbre non inversé, ce tri est très rapide pour les ensembles déjà presque triés, sinon, il est en O(n \log n). Tri en place mais pas stable

à toi de voir les conditions initiale afin de définir le meilleur choix

[nadirmabed]

voila exemple de tri

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
 
 
AlgoBox : tri par insertion
program tri(input,output
 
Code de l'algorithme
1   VARIABLES
2     i EST_DU_TYPE NOMBRE
3     j EST_DU_TYPE NOMBRE
4     rangmin EST_DU_TYPE NOMBRE
5     min EST_DU_TYPE NOMBRE
6     t EST_DU_TYPE LISTE
7   DEBUT_ALGORITHME
8     AFFICHER "introduisezz les element du tableau"
9     POUR i ALLANT_DE 1 A 5
10      DEBUT_POUR
11      LIRE t[i]
12      FIN_POUR
13    POUR i ALLANT_DE 1 A 5
14      DEBUT_POUR
15      min PREND_LA_VALEUR t[i]
16      rangmin PREND_LA_VALEUR i
17      POUR j ALLANT_DE i+1 A 5
18        DEBUT_POUR
19        SI (t[j]<min) ALORS
20          DEBUT_SI
21          min PREND_LA_VALEUR t[j]
22          rangmin PREND_LA_VALEUR j
23          FIN_SI
24        FIN_POUR
25      t[rangmin] PREND_LA_VALEUR t[i]
26      t[i] PREND_LA_VALEUR min
27      FIN_POUR
28    
29    POUR i ALLANT_DE 1 A 5
30      DEBUT_POUR
31      AFFICHER t[ i ]
32      FIN_POUR
33  FIN_ALGORITHME
 
Résultats
***Algorithme lancé***
introduisezz les element du tableau
Entrer le terme de rang i de la liste t : 555
Entrer le terme de rang i de la liste t : 555
Entrer le terme de rang i de la liste t : 2122
Entrer le terme de rang i de la liste t : 2555.
Entrer le terme de rang i de la liste t : 52
52
555
555
2122
2555
***Algorithme terminé***
 
Généré par AlgoBox

[zaza576]

Tu vas pas tous nous les poster sur cette discussion j'espère ?
De plus, cela ne répond pas du tout à la question de base !

[kolodz]

Les algorithme de tri sont une base. Cependant, c'est leur apprentissage est plus présent pour introduire la notion de complexité d'un algorithme, ainsi que la capacité d'analyse des algorithmes de manière général.
Il est très peu probable qu'un développeur ai à coder un algorithme de tri générique tel qu'on le présente en classe. Il y a de plus en plus d'API qui proposent un tri à partir d'une fonction de comparaison et se charge de faire la partie algorithmique.

Cependant, il sera peut-être confronté à un traitement trop long dû à un algorithme ayant une complexité trop élevée. A ce moment là, il lui sera nécessaire de comprendre en quoi cette algorithme est consommateur et les éventuelles solutions possible. (Et potentiellement reprendre ce qui existe dans les algorithmes de tri.)

Donc les algorithmes de tri, à comprendre plus qu'à connaitre.

Cordialement,
Patrick Kolodziejczyk.