Un mien ami, qui fut mien camarade de cours quand nous usions les bancs de la fac d'info de Namur, est il me semble l'instigateur de la 'pataprogrammation, qui est à la programmation ce que la 'pataphysique est à la physique. Je pense que l'amie Wikipedia saura mieux que moi vous expliquer ce qu'est cette fameuse 'pataphysique, retenez surtout que son inventeur est le père de Ubu, ça donne le ton.
Ce joyeux farfelu a donc déliré un jour et inventé le "tri à gobelets" qui est sans aucun doute le moins efficace des algorithmes de tri. L'idée est simple: permutons deux éléments du tableau à trier, choisis au hasard, et répétons l'opération jusqu'à ce que le tableau soit effectivement trié.
Bon, intuitivement c'est une atrocité cet algorithme, mais en fait c'est une atrocité à quel point? Comme le dit son auteur, il s'exécute de façon pas trop péniblement lente pour des tableaux de petite taille, mais avec peu de chance on peut y perdre beaucoup de temps. De plus, l'alogorithme n'a aucune garantie de terminaison autre que la fin des temps. Brillant! Donc pour avoir une mesure, j'ai pondu le programme suivant:
#! /usr/bin/python
# Implementation de l'algorithme de tri par gobelets, invente par Benoit Vleminckx
# http://www.javafr.com/codes/TRI-GOBELET-BEAKER-SORT_48639.aspx
import random
def is_sorted(tab):
""" renvoie True ssi tab est trie par ordre croisant """
for i in range (0,len(tab)-1):
if tab[i] > tab[i+1]:
return False
return True
def beakersort(tab):
"""Trie le tableau tab par l'algorithme du tri a gobelets"""
# pour la science
iterations = 0
while not is_sorted(tab):
iterations += 1
# determination de deux indices aleatoires differents
index1 = -1
index2 = -1
while (index1 == index2):
index1 = random.randint(0,len(tab)-1)
index2 = random.randint(0,len(tab)-1)
# permutation des elements a ces indices
tab[index1],tab[index2] = tab[index2],tab[index1]
print len(tab), iterations
return tab
# Mesures hautement scientifiques!
for tablength in range (3,11):
for testnum in range (0,100):
testtab = range(0,tablength)
random.shuffle(testtab)
beakersort(testtab)
Remarquons que j'y suis optimiste puisque je suppose que chaque application de l'algorithme va effectivement se terminer un jour. Il faut savoir vivre dangereusement parfois...
Conclusion? Pas brillantes du tout. En résumé pour des tailles de tableau allant de 3 à 10 on obtient ceci (valeurs exprimées en nombre de permutations avant achèvement):
| Longueur | Minimum | Maximum | Moyenne |
|---|---|---|---|
| 3 | 0 | 30 | 5 |
| 4 | 0 | 105 | 22 |
| 5 | 0 | 659 | 117 |
| 6 | 7 | 3779 | 917 |
| 7 | 81 | 23892 | 5096 |
| 8 | 330 | 199540 | 38792 |
| 9 | 11321 | 1791937 | 339068 |
| 10 | 21080 | 17668142 | 4145666 |
Magnifiquement inefficace, n'est-ce pas?
...la suite par ici...
