Quicksort expliqué aux enfants

16

L'année dernière, je lisais un article fantastique sur «La mécanique quantique pour les jardins d'enfants» . Ce n'était pas du papier facile.

Maintenant, je me demande comment expliquer le tri rapide dans les mots les plus simples possibles. Comment puis-je prouver (ou au moins une onde de main) que la complexité moyenne est , et quels sont les meilleurs et les pires cas, à une classe de jardin d'enfants? Ou du moins à l'école primaire?O(nJournaln)

jonaprieto
la source
9
Vous voulez prouver la complexité du tri rapide ... à un groupe de trois ans ...? Bonne chance.
2
Essayez d'utiliser leur langage, le problème est que c'est très limité et biologiquement ils ne sont pas prêts pour cette complexité. Les étapes suivantes, comme dans un algorithme, ne sont pas entièrement développées avant l'âge de six ou sept ans. Vous faites face à un défi biologique.
4
Je ne le recommanderais pas réellement pour la maternelle, mais recherchez sur YouTube pour le tri rapide (et d'autres algorithmes de tri) fournit de nombreuses bonnes représentations. Personnellement, je préfère les danses folkloriques hugariennes. Voir youtube.com/watch?v=ywWBy6J5gz8 .
2
Le document dont vous parlez a un titre accrocheur mais un contenu très complexe comme Hilbert Space Model, alors que voulez-vous vraiment?
2
Je renoncerais à essayer d'expliquer pleinement le tri rapide, et j'essaierais plutôt de donner aux enfants une compréhension de «diviser pour mieux régner». Même s'ils ne sont pas assez vieux pour bloquer complètement la récursivité, l'idée de décomposer un gros problème en problèmes plus petits serait vraiment valable. Personnellement, je prendrais une solide compréhension fondamentale de la division et de la conquête chaque jour sur une notion incomplète d'algorithmes complexes.
Vincent Gable

Réponses:

14

À la base, Quicksort est le suivant:

  1. Prenez le premier objet.
  2. Déplacez tout moins que ce premier élément vers la gauche de lui, tout plus grand vers la droite (en supposant l'ordre croissant).
  3. Reculez de chaque côté.

Je pense que chaque enfant de 4 ans sur la planète pourrait faire 1 et 2. La récursivité pourrait prendre un peu plus d'explications, mais ne devrait pas être si difficile pour eux.

  1. Répétez sur le côté gauche, en ignorant la droite pour l'instant (mais rappelez-vous où était le milieu)
  2. Continuez à répéter avec les côtés gauche jusqu'à ce que vous n'obteniez rien. Revenez maintenant au dernier côté droit que vous avez ignoré et répétez le processus.
  3. Une fois que vous n'avez plus de côtés droit et gauche, vous avez terminé.

Quant à la complexité, le pire des cas devrait être assez facile. Considérez simplement un tableau déjà trié:

1 2 3 4
  2 3 4
    3 4
      4

Assez facile à voir (et à prouver) que c'est .12n2

Je ne connais pas la preuve de cas moyen, donc je ne peux pas vraiment faire de suggestion à ce sujet. On pourrait dire que dans un tableau de longueur non trié la probabilité de choisir le plus petit ou le plus grand élément est de 2l , alors ...?2n

Kevin
la source
Peut-être que la récurrence (d & c) est la meilleure et la plus naturellement expliquée par le parallélisme inhérent.
Raphael
2
Je serais d'accord. Mon instinct était d'utiliser une métaphore pour donner les deux piles à vos amis.
Christian Mann
3
Je prétends que les enfants de quatre ans sont (à de possibles exceptions près) fondamentalement incapables de saisir la récursivité, peu importe vos efforts. Le cerveau n'est tout simplement pas assez mature. Il y a des phases bien définies dans le développement du cerveau, par exemple le moment où les enfants deviennent conscients d'eux-mêmes, où ils deviennent conscients des conséquences futures des actions en cours, et où ils comprennent d'abord le sarcasme qui suit un calendrier étroitement contrôlé qui ne peut pas être réorganisé volontairement et est hautement conservé chez les enfants. Je crois que la compréhension de la récursion tombe dans la même catégorie.
Konrad Rudolph
16

Quicksort est en fait assez facile à comprendre, s'ils comprennent le comptage de base et la division par 2. Créez un tas de cartes flash X, numérotez-les 1 - X et mélangez-les. Alors voici l'explication:

OK, nous avons ici ce jeu de cartes (disons 20). Nous voulons les mettre en ordre, donc 1 est d'abord, puis 2, puis 3, et ainsi de suite. Voici un moyen très rapide de le faire.

Tout d'abord, passons par ce jeu et en faisons deux piles. La moitié de 20 est 10, donc tout ce qui dépasse 10 va dans cette pile à droite, et tout ce qui est plus petit va dans cette pile à gauche. (Assurez-vous de démontrer que vous allez.)

Maintenant, faisons la même chose avec les piles plus petites. Quelle est la moitié de 10? (Quelqu'un dit "cinq!") C'est vrai! Donc, tout ce qui dépasse 5 va dans cette pile à droite, et tout ce qui est plus petit va dans cette pile à gauche.

Et ici, nous avons le groupe qui est plus grand que 10. Donc, la moitié de 10 est 5, et qu'est-ce que 10 plus 5? (Quelqu'un dit "quinze!") C'est vrai! Donc, tout ce qui dépasse 15 va dans cette pile à droite, et tout ce qui est inférieur à 15 va dans cette pile à gauche.

Et maintenant, les piles deviennent suffisamment petites pour que vous puissiez facilement les regarder et les mettre en ordre. Regardez, nous avons ici 2, 4, 5, 3, 1. Nous les basculons donc comme ça, et vous pouvez voir 1, 2, 3, 4, 5. Faisons donc la même chose avec les autres piles, puis nous mettons simplement les piles en ordre, et regardons! Ils sont en ordre de 1 à 20!

Toutes nos félicitations. Vous venez d'apprendre à un groupe d'enfants les principes de base d'un algorithme de tri rapide adaptatif! Vous pouvez aller un peu plus loin que cela en fonction de la maturité mentale, mais aller bien au-delà de ce point nécessite une certaine compréhension de la logique formelle.

Quant à prouver sa complexité, c'est plus délicat. C'est l'une des choses qui nécessite une logique formelle, et ils devront comprendre les principes de base de la notation big-O en premier lieu. Vous voudrez peut-être retenir cette partie au début.

Mason Wheeler
la source
Je ne pense pas que votre exemple ne soit pas bon car vous triez essentiellement sur des clés, pas sur des valeurs, et vous ne pouvez savoir ce qui est en position 15 qu'en ayant déjà trié.
Thorbjørn Ravn Andersen
@ Thorbjørn: Qui a dit quoi que ce soit sur les paires clé / valeur? Il s'agit d'un simple type entier pour expliquer le concept de base.
Mason Wheeler
Réfléchir à l'algorithme que vous décrivez n'est pas un tri rapide, car vous n'utilisez pas d'élément pivot.
Thorbjørn Ravn Andersen
1
@ ThorbjørnRavnAndersen: Bien sûr qu'il le fait; c'est juste qu'il sait quels éléments sont là pour pouvoir choisir la médiane.
Raphael
@Raphael et leur distribution. Les cartes peuvent avoir n'importe quelle valeur et couleur et avoir juste un autocollant avec leur nombre entre 1 et 20. D'où ma référence à la clé / index et non à la valeur.
Thorbjørn Ravn Andersen
2

Que dis-tu de ça?

Computer Science Unplugged - Algorithmes de tri

Il ne couvre pas tout à fait toutes vos questions, mais c'est un bon début.

Plus de ressources sur ce sujet sont liées ici .

Ils ont également mis à disposition une vidéo expliquant les algorithmes de tri (tri rapide inclus) ici . Cette vidéo aide vraiment à comprendre la différence entre les différents algorithmes de tri pour les jeunes enfants.

TimB
la source
génial! Assez facile à comprendre.
Mayur Patil
1

Voir la beauté graphique de cette petite démo .

tri rapide.

gbjbaanb
la source
1
Je pense que cela pourrait être trop abstrait pour les enfants.
Raphael
3
Pour ne pas m'embarrasser, mais je n'ai pas compris ce graphique jusqu'à ce qu'on m'explique enfin le tri rapide en classe.
Christian Mann
Avoir un +1 parce que c'est ce qui m'est venu à l'esprit lorsque j'ai lu la question, mais je suis ensuite un apprenant visuel.
Joshua Drake
3
C'est vraiment une mauvaise façon d'expliquer comment fonctionne le tri rapide . Si vous connaissez déjà le tri rapide, vous pouvez confirmer que cette animation concerne le tri rapide. Si vous ne connaissez pas le tri rapide, il ne dit rien, sauf que le tri rapide est un algorithme de tri assez rapide qui utilise de la magie. Selon qui est le public, vous pourrez peut-être motiver le public à en apprendre davantage sur le tri rapide en montrant cette animation, mais cela n'explique rien d'important sur son fonctionnement.
Tsuyoshi Ito
L'animation est plutôt sympa mais elle est jusqu'à présent compréhensible pour un débutant même pour un étudiant de premier cycle à première vue.
jonaprieto du