Nouveaux tris révolutionnaires

[Dusty]

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.

Le “Gnome sort” est basé sur la technique utilisé par le nain de jardin néerlandais. Voici comment le nain de jardin opère pour trier une lignée de pots de fleur. En premier lieu, il regarde le pot de fleur avant et après lui; si ils sont dans l’ordre il saute le pot devant lui, sinon il inverse les deux pots de fleurs et fait un saut de pot de fleur en arrière. Il continue l’opération jusqu’à ce qu’il atteigne le dernier pot.

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

[Sans-Nom]

Le tri de l’homme bourré a l’air aussi efficace que son titre…

[deltree]

Le tri des nains de jardins a l’air très proche d’un tri à bulle donc aussi inefficace, quand à l’autre, un tri en o(n²) n’a rien de révolutionnaire, puisque les tri classiques sont en o( n.ln(n) ) (donc moins).:

par contre en cumulant le drunk man sort avec un qsort pour les grandes tailles, on peut obtenir des résultats intéressants, car le qsort peut dériver en temps d’exécution si l’ordre d’origine n’est pas aléatoire.

enfin pour moi un tri révolutionnaire c’est en o(n) pour le cas moyen, pas pour le meilleurs de cas, il y a le “flash sort” ou “tri par classement” qui est en o(n) sous certaines conditions, et qui est plus ou moins protégé au niveau des droits d’auteurs…

[Sans-Nom]

Y a le delete sort aussi, en O(1) celui là Tu supprimes tous les éléments, et tu te casses sans laisser de preuves! Efficace, car y a plus rien à trier ensuite

[InSiderZ]

Y a le delete sort aussi

Va savoir pourquoi, j’ai compris le deltree sort… :sweet:

[deltree]

c’est toi quoi sort :na:

[Sans-Nom]

Ben un deltri…

<-- []

[Dusty]

Le tri des nains de jardins a l’air très proche d’un tri à bulle donc aussi inefficace, quand à l’autre, un tri en o(n²) n’a rien de révolutionnaire, puisque les tri classiques sont en o( n.ln(n) ) (donc moins).:

Le tri des nains de jardin sont en O(n) dans le cas d’une liste déjà triée (O(n*n) pour le tri à bulle!). Je dirais que ce tri se rapproche plus du tri par insertion (qui n’est certes pas optimal… mais qui est utilisé pour le tri de petites listes?)

par contre en cumulant le drunk man sort avec un qsort pour les grandes tailles, on peut obtenir des résultats intéressants, car le qsort peut dériver en temps d’exécution si l’ordre d’origine n’est pas aléatoire.

Ce serait pas toi le “drunken man” :paf:, parce que je comprends pas ce que tu dis :peur:.
Ce tris de l’homme bourré est franchement pourrave (rien qu’à voir le pire des cas…).

enfin pour moi un tri révolutionnaire c’est en o(n) pour le cas moyen, pas pour le meilleurs de cas, il y a le “flash sort” ou “tri par classement” qui est en o(n) sous certaines conditions, et qui est plus ou moins protégé au niveau des droits d’auteurs…

Y a aussi le “Radix sort”. Mais là ça devient trop sérieux pour moi :nexath
Mais il faut préciser que le meilleur des tris sera en O(n*lg(n)). Après comme tu le dis: “sous certaines conditions” on peut faire mieux (d’ailleurs ces tris m’intéressent beaucoup, je vais faire quelques recherches dessus)

Et sinon je dois préciser que à la base ce topic était juste une grosse blague et pas un truc pour partager des trucs sérieux (juste de l’humour de g33k) bien que ces tris existent bien!
Edité le 16/07/2007 à 21:44

[deltree]

Ah… de l’humour de geek, continue sur le topic de discussion, je comprend pas tous ce qu’ils disent, tu me traduira

Moi bourré, meuh non :ennuye:
Depuis que j’ai appris en cours de stat, qu’en envoyant son courrier à des adresses aléatoire, il y avait une probabilité non-nulle qu’ils arrivent aux bons destinataires, je fait tout mon courrier comme ça!

[InSiderZ]

Moi bourré, meuh non :ennuye:

on n’y crois pas :o :kimouss: