Lors de ma promenade matinale sur internet, j’ai rencontré deux tris qui, à mon avis, vont chambouler le monde de l’informatique (je tiens à vous les faire partager en primeur)
Le premier est un tri déjà recensé par wikipédia et présenté sur le site d’une prestigieuse université néerlandaise. Il s’est inspiré de la technique utilisée par les nains de jardin hollandais pour trier les pots de fleurs.
Voici une présentation de ce tri trouvée sur http://www.cs.vu.nl/~dick/gnomesort.html et traduit par mes (mauvais?) soins.
Tenez vous bien, ce tris est quand même en O(n) dans le meilleure des cas et il est stable (je ne vous parlerai pas du plus mauvais cas :nexath).
Le deuxième tri est un tri inventé par Knuth (en personne!) qui permet de trier une liste d’élément en… O(nn!) dans le cas moyen (très proche de O(nn) sauf qu’il y a un point d’exclamation en plus :paf:). Il consiste à mélanger aléatoirement une liste et tester si elle est triée (et répéter l’opération jusqu’à ce que la liste soit triée).Ce tri s’appel le bogosort, aussi nommé: stupid sort ou drunk man sort (le tri de l’homme bourré).
Concernant le pire de cas je n’en perlerai pas, parce que sur wikipédia ils disent que c’est “unbounded” :paf: (oui ok, c’est vrai que ça peut être problématique…).
Bon, j’avoue, ce tri a été inventé à titre pédagogique. Mais vous l’aurez compris, l’avenir est dans le gnome sort et le bogo sort.
Avouez que vous êtes bluffés par la qualité et la rapidité de ces tris?
Edité le 15/07/2007 à 18:01