Retour sur le tri à gobelets
Au détour d'une conversation au boulot un collègue parlait d'algorithmes absurdes et en arrivait à mentionner l'idée folle d'un tri qui se ferait en permutant des éléments au hasard, ce qui m'a beaucoup amusé puisque c'est quelque chose que j'ai déjà mentionné ici.
Et c'est bien de ça qu'il s'agit : étant donnée une liste d'entier, les trier par ordre croissant en permutant au hasard des éléments deux à deux jusqu'à ce que la liste soit triée. C'est idiot, c'est absurde, et ça prend un temps qu'on ne peut pas déterminer d'avance et qui peut même être infini.
Du coup j'ai réimplémenté ça sous forme de petit programme CLI pour qu'on puisse le précéder de time
pour mesurer l'ampleur du désastre et les grands écarts entre plusieurs exécutions sur exactement la même liste en entrée. C'est en Python comme la dernière fois, mais aussi en PHP et en JavaScript (via NodeJS).
Et comme on est en 2020, le code est sur GitHub