Vraiment cool, si tu pouvais aborder des notions intermédiaires comme celle-ci avec cette clareté ça serais vraiment super car une explication visuelle avec une personne derrière est souvent très cool pour comprendre précisément le fonctionnement
Petit commentaire en passant sur le fait qu'un algo de tri par comparaison a une complexité en Omega(n.log n). On peut représenter abstraitement un algo de tri par comparaison par un arbre. Au départ, l'algo fait une première comparaison en L[i] et L[j]. Si L[i est supérieur à L[j], alors l'algo va faire des trucs et sinon, il va faire des machins. Dans le premier cas, l'algo va faire une nouvelle comparaison et brancher. Idem dans le second cas. On a un arbre des comparaisons utilisées qui apparaît. L'exécution de l'algo sur une liste L correspond à un parcours dans cet arbre et la liste L correspond à une feuille de l'arbre. La complexité dans le pire des cas correspond à le branche la plus longue de l'arbre. Un algo efficace va correspondre à un arbre le plus équilibré possible. Maintenant, on sait qu'un arbre binaire de hauteur h a 2^h feuilles. Donc la complexité optimale d'un algo de tri est log(nombre de listes de taille n). Or, il y a n! listes de taille n. Un algo de tri a donc une complexité au minimum de log(n!)=n.log(n)(1+o(1)). Paf.
Rien à voir avec le sujet (très bien expliqué par ailleurs), mais j'ai adoré le choix de musique de fond, je regardais cette vidéo en pleine nuit à défaut de pouvoir m'endormir et combiné à la voix posée ça a réussi lol
On parle beaucoup trop souvent de complexité comme indicateur absolue de la performance, on dit par exemple qu'une HashMap est plus rapide qu'une recherche linéaire, vu que le premier est O(1) et le deuxieme O(n) dans le pire cas, mais ça dépend beaucoup du contexte, pour un petit nombre d'élément une recherche linéaire battera une HashMap a pleine couture, c'est la même chose pour les algo de trie, insertion sort a beau être O(n²), la grande majorité des algo O(nlogn) l'utilise comme sous programme vu que son cout de mise en place est presque inexistant, donc pour un petit nombre d'element il est extremement efficace. La grande majorité des algo O(nlogn) ne sont que des strategies pour diviser la liste en plusieurs petites listes, ensuite triée par des algo O(n²). Le complexité ne fait que donné une idée de la courbe de vitesse, il se peut qu'un algo O(n) ne devienne plus rapide qu'un algo O(n²) qu'a partir de n = 100, voir n = 1000, ou plus encore. Il faut tester, et pas uniquement se fier a la complexitée.
très bonne vidéo et c'est marrant des objections que j'avais tu les as formulées aussi. Es ce que tu peux nous donner la référence de la vidéo de la fin (à partir de 7:49 je trouve ça trop stylé et hypnotique)
Excellent, on sent l'école d'ingés ou la prépas mp2i 👀Tu pourrais faire une vidéo sur l'algo de Dijkstra (voir A*) un jour ? J'ai fait des recherches dessus il y a pas longtemps et les vidéos en FR sont pas terribles, ça pourrait marcher
Je voudrais quand même souligner qu'il existe l'algorithme random sort, qui redéfini le placement des éléments à trier aléatoirement. La probabilité qu'il ait fini dès la première itération est non nulle, ce qui en fait l'algorithme le plus rapide et ce peu importe le nombre d'éléments à trier (si on a de la chance)
plus rapide != meilleure complexité De plus, le trie qui consiste a renvoyer le tableau directement est encore plus rapide (dans le cas ou le tableau est trié)
Super vidéo avec des visuels très agréable et épuré. Juste une petite typo : A 7:29 tu dis "par conséquence" alors que cest "par conséquent". Sinon c'est "en conséquence"
Le tri radix se sert du chiffre extrait dans le nombre pour ranger ce dernier dans la liste associée dans une liste mère -- il utilise ce chiffre comme index, comme clé. Une fois tous les nombres rangés, il prend les nombres de chaque liste, un à un, dans l'ordre et les replace dans la liste source. L'opération est répété autant de fois qu'il y a de chiffres pour la base spécifiée. Par exemple, en radix base 2, on aurait ainsi ceci en Python : buckets = [[], []] Exprimé de manière générique : buckets = [[]] * b # base Ainsi, un nombre n et son chiffre m associé serait rangé de cette manière là : buckets[n % b].append(n) Il ne restera plus qu'à intérer dans l'ordre dans chacune de ces listes de `bucket` et répèter l'opération ! Il n'y a pas donc vraiment besoin de faire un tri par comptage après coup (ou alors j'ai compris de travers ?)
Moi, j'ai un tri encore plus rapide. Certes, il est un peu spécialisé mais il est vraiment très très rapide. On ne peut pas faire plus rapide. def tri(L): return L Si on lui donne une liste triée, ben il trie la liste. Bien évidemment, cet exemple est totalement caricatural. Mais il montre bien le problème. Si on veut un tri général qui ne soit jamais mauvais, alors un tri par comparaison en O(n.log n) est LA solution. En revanche, si on a des informations supplémentaires, alors on peut éventuellement faire des trucs spécifiques plus efficaces. Le problème, c'est qu'il est irréaliste de demander aux gens d'être des spécialistes des tris, des structures de données, de réseau, de base de données, de framework web... Donc on popularise surtout des algos généralistes.
Je ne me souviens pas avoir entendu parler de l'algo de tri comptage, mais peut-être que si. C'est vraiment astucieux. Par contre pour le radix, je ne comprends pas pourquoi on ne commence pas plutôt par les poids forts.
Hum, je ne pense pas qu'on puisse parler de complexité linéaire pour ces algo par rapport à la taille de l'entrée. Pour le count sort: comme vous le dites dans la vidéo, il y a un k=b^(max[n_i]) avec b la base et n_i les nombres à trier... Je parlerais plus d'algo exponentiel ou quadratique. Il y a plein de cas où il n'est pas plus rapide en moyenne. Mais à part cet abus de langage bonne video.
Bonne introduction à ces algorithmes. Pour les anglophones, explication simple et détaillée du fonctionnement du counting sort et du radix sort : czcams.com/video/ujb2CIWE8zY/video.html
Ma question. Serait-il possible de combiner deux algorithm de type block sort par exemple et d'utiliser sa propriété n en temps de complexité ? Et d'associer avec quick sort et d'utiliser sa propriété logarithmique + n. On pourrait par exemple segmenter avec block sort la liste pour finalement trier en petite partie les segments afin de justement utiliser sur les petits segments les propriété nlogn. Je sais pas si ce que je dis est faux, je peux me tromper. J'ai essayer sur desmos et apparament nlogn est plus rapide sur des tris de très petits segment que N. Corrige moi sans autre si je me trompe. Sinon, vidéo très intéressante et un nouvel abonné. 😀
salut ! merci pour ton retour :) je ne sais pas si j'ai bien compris ta question, mais de ce que j'ai compris, tu me demandes si on peut utiliser quick sort avec block sort pour accélérer les calculs ? A ça je repondérai oui tu peux. D'après Wikipédia, il est recommandé d'utiliser le tri par insertion. Je ne suis pas exactement sûr pourquoi mais, je pense que pour la même raison que Bucket sort dans ma vidéo, cet algorithme est simple, adapté pour des petit paquets, stable, in-place (c'est à dire O(1) en complexité mémoire), or quick sort n'a pas ces propriétés et est adapté pour des grand paquets en vue de sa complexité moyenne. Après la comparaison nlogn et n n'a pas vraiment de sens pour des petits nombres car justement, la notation "grand O" mesure la complexité pour un très grand nombre : O(n²+n) peut être transformé en O(n²). Ca dépend de la base du logarithme, de constante de multiplication... Il faut alors plutôt comparer le nombre d'instructions.
En vrai si tu enregistre des donnée en memoire pour ensuite les trier au besoin le meilleur moyen c'est de faire un heap sort Tu inseres les element dans une priority queue et tu le tri quand tu en as besoin C'est la même complexité que Merge sort Et ça n'a pas l'inconvénient du quick sort qui peut etre de O(n²) dans le pire des cas
C'est cool de voir ce genre de vidéos apparaître en français
Vraiment cool, si tu pouvais aborder des notions intermédiaires comme celle-ci avec cette clareté ça serais vraiment super car une explication visuelle avec une personne derrière est souvent très cool pour comprendre précisément le fonctionnement
shuuuuuuuush video incroyable, le montage est vrm bien, ça me fait pensé à Manim un peu + l'animation de fin g grv kifé
Très bonne vidéo, attention tout de même à conserver le nom des algorithmes en anglais pour plus de simplicité ! Très bon montage.
Excellente vidéo avec de très bonnes illustrations, merci!
Merci beaucoup
Gilles
Incroyable ta video !
Très bonnes explications et très bons visuels, ça aide vraiment.
Petit commentaire en passant sur le fait qu'un algo de tri par comparaison a une complexité en Omega(n.log n).
On peut représenter abstraitement un algo de tri par comparaison par un arbre.
Au départ, l'algo fait une première comparaison en L[i] et L[j]. Si L[i est supérieur à L[j], alors l'algo va faire des trucs et sinon, il va faire des machins.
Dans le premier cas, l'algo va faire une nouvelle comparaison et brancher. Idem dans le second cas. On a un arbre des comparaisons utilisées qui apparaît.
L'exécution de l'algo sur une liste L correspond à un parcours dans cet arbre et la liste L correspond à une feuille de l'arbre. La complexité dans le pire des cas correspond à le branche la plus longue de l'arbre. Un algo efficace va correspondre à un arbre le plus équilibré possible.
Maintenant, on sait qu'un arbre binaire de hauteur h a 2^h feuilles. Donc la complexité optimale d'un algo de tri est log(nombre de listes de taille n). Or, il y a n! listes de taille n. Un algo de tri a donc une complexité au minimum de log(n!)=n.log(n)(1+o(1)).
Paf.
Merci tu m'as fait comprendre avec beaucoup d'aisance un truc j'ai galéré a comprendre il y a 3 ans
Rien à voir avec le sujet (très bien expliqué par ailleurs), mais j'ai adoré le choix de musique de fond, je regardais cette vidéo en pleine nuit à défaut de pouvoir m'endormir et combiné à la voix posée ça a réussi lol
Incroyable
On parle beaucoup trop souvent de complexité comme indicateur absolue de la performance, on dit par exemple qu'une HashMap est plus rapide qu'une recherche linéaire, vu que le premier est O(1) et le deuxieme O(n) dans le pire cas, mais ça dépend beaucoup du contexte, pour un petit nombre d'élément une recherche linéaire battera une HashMap a pleine couture, c'est la même chose pour les algo de trie, insertion sort a beau être O(n²), la grande majorité des algo O(nlogn) l'utilise comme sous programme vu que son cout de mise en place est presque inexistant, donc pour un petit nombre d'element il est extremement efficace. La grande majorité des algo O(nlogn) ne sont que des strategies pour diviser la liste en plusieurs petites listes, ensuite triée par des algo O(n²). Le complexité ne fait que donné une idée de la courbe de vitesse, il se peut qu'un algo O(n) ne devienne plus rapide qu'un algo O(n²) qu'a partir de n = 100, voir n = 1000, ou plus encore. Il faut tester, et pas uniquement se fier a la complexitée.
Super vidéo.
très bonne vidéo et c'est marrant des objections que j'avais tu les as formulées aussi. Es ce que tu peux nous donner la référence de la vidéo de la fin (à partir de 7:49 je trouve ça trop stylé et hypnotique)
Merci pour ton retour :) la référence de la vidéo : czcams.com/video/BeoCbJPuvSE/video.html
Avec quoi tu fais le visuel / les animations de tes vidéos ? C'est vraiment impressionnant la qualité
Merci
je fais le montage sur After Effects
Excellente vidéo!
Excellent, on sent l'école d'ingés ou la prépas mp2i 👀Tu pourrais faire une vidéo sur l'algo de Dijkstra (voir A*) un jour ? J'ai fait des recherches dessus il y a pas longtemps et les vidéos en FR sont pas terribles, ça pourrait marcher
merci pour ton retour ;) Personnellement j'ai appris et j'apprends en autodidacte, et merci pour ta suggestion !
Je voudrais quand même souligner qu'il existe l'algorithme random sort, qui redéfini le placement des éléments à trier aléatoirement. La probabilité qu'il ait fini dès la première itération est non nulle, ce qui en fait l'algorithme le plus rapide et ce peu importe le nombre d'éléments à trier (si on a de la chance)
plus rapide != meilleure complexité
De plus, le trie qui consiste a renvoyer le tableau directement est encore plus rapide (dans le cas ou le tableau est trié)
@@dasny5841 je ne suis pas sur de comprendre ta remarque dans la première partie de ton commentaire ?
Mais bien vu pour la seconde mdr
Super vidéo avec des visuels très agréable et épuré.
Juste une petite typo : A 7:29 tu dis "par conséquence" alors que cest "par conséquent". Sinon c'est "en conséquence"
Très bonne vidéo !
MA vie de dev 6h15 sur les tris 👀 T'as vu l'algo de l'IA Google a sorti sur une nouvelle solution de tri ?
Par encore vue, je vais aller voir ça après. Merci pour ta suggestion !
stiley, bravo pour la vidéo c'est quali
Le tri radix se sert du chiffre extrait dans le nombre pour ranger ce dernier dans la liste associée dans une liste mère -- il utilise ce chiffre comme index, comme clé. Une fois tous les nombres rangés, il prend les nombres de chaque liste, un à un, dans l'ordre et les replace dans la liste source. L'opération est répété autant de fois qu'il y a de chiffres pour la base spécifiée.
Par exemple, en radix base 2, on aurait ainsi ceci en Python :
buckets = [[], []]
Exprimé de manière générique :
buckets = [[]] * b # base
Ainsi, un nombre n et son chiffre m associé serait rangé de cette manière là :
buckets[n % b].append(n)
Il ne restera plus qu'à intérer dans l'ordre dans chacune de ces listes de `bucket` et répèter l'opération !
Il n'y a pas donc vraiment besoin de faire un tri par comptage après coup (ou alors j'ai compris de travers ?)
Moi, j'ai un tri encore plus rapide. Certes, il est un peu spécialisé mais il est vraiment très très rapide. On ne peut pas faire plus rapide.
def tri(L):
return L
Si on lui donne une liste triée, ben il trie la liste.
Bien évidemment, cet exemple est totalement caricatural. Mais il montre bien le problème.
Si on veut un tri général qui ne soit jamais mauvais, alors un tri par comparaison en O(n.log n) est LA solution. En revanche, si on a des informations supplémentaires, alors on peut éventuellement faire des trucs spécifiques plus efficaces.
Le problème, c'est qu'il est irréaliste de demander aux gens d'être des spécialistes des tris, des structures de données, de réseau, de base de données, de framework web... Donc on popularise surtout des algos généralistes.
Je ne me souviens pas avoir entendu parler de l'algo de tri comptage, mais peut-être que si. C'est vraiment astucieux. Par contre pour le radix, je ne comprends pas pourquoi on ne commence pas plutôt par les poids forts.
Hum, je ne pense pas qu'on puisse parler de complexité linéaire pour ces algo par rapport à la taille de l'entrée. Pour le count sort: comme vous le dites dans la vidéo, il y a un k=b^(max[n_i]) avec b la base et n_i les nombres à trier... Je parlerais plus d'algo exponentiel ou quadratique.
Il y a plein de cas où il n'est pas plus rapide en moyenne.
Mais à part cet abus de langage bonne video.
Salut j'aimerais savoir quel outil tu utilise pour afficher les listes et les nombres merci bcp !
J'utilise After Effects
Bonne introduction à ces algorithmes.
Pour les anglophones, explication simple et détaillée du fonctionnement du counting sort et du radix sort : czcams.com/video/ujb2CIWE8zY/video.html
c est super
propre
Ma question. Serait-il possible de combiner deux algorithm de type block sort par exemple et d'utiliser sa propriété n en temps de complexité ? Et d'associer avec quick sort et d'utiliser sa propriété logarithmique + n. On pourrait par exemple segmenter avec block sort la liste pour finalement trier en petite partie les segments afin de justement utiliser sur les petits segments les propriété nlogn. Je sais pas si ce que je dis est faux, je peux me tromper. J'ai essayer sur desmos et apparament nlogn est plus rapide sur des tris de très petits segment que N. Corrige moi sans autre si je me trompe. Sinon, vidéo très intéressante et un nouvel abonné. 😀
salut ! merci pour ton retour :)
je ne sais pas si j'ai bien compris ta question, mais de ce que j'ai compris, tu me demandes si on peut utiliser quick sort avec block sort pour accélérer les calculs ? A ça je repondérai oui tu peux. D'après Wikipédia, il est recommandé d'utiliser le tri par insertion. Je ne suis pas exactement sûr pourquoi mais, je pense que pour la même raison que Bucket sort dans ma vidéo, cet algorithme est simple, adapté pour des petit paquets, stable, in-place (c'est à dire O(1) en complexité mémoire), or quick sort n'a pas ces propriétés et est adapté pour des grand paquets en vue de sa complexité moyenne. Après la comparaison nlogn et n n'a pas vraiment de sens pour des petits nombres car justement, la notation "grand O" mesure la complexité pour un très grand nombre : O(n²+n) peut être transformé en O(n²). Ca dépend de la base du logarithme, de constante de multiplication... Il faut alors plutôt comparer le nombre d'instructions.
En vrai si tu enregistre des donnée en memoire pour ensuite les trier au besoin le meilleur moyen c'est de faire un heap sort
Tu inseres les element dans une priority queue et tu le tri quand tu en as besoin
C'est la même complexité que Merge sort
Et ça n'a pas l'inconvénient du quick sort qui peut etre de O(n²) dans le pire des cas
L’algorithme qui mélange la liste aléatoirement en meilleur cas a O(n)
Édit: la complexité moyenne est de O(n fois n!) 😅
merci pour la vidéo mais la musique c est pas top