13/12/2009

Exercice de 'pataprogrammation: le tri à gobelets

Tiens et si on parlait d'informatique, pour changer un peu, et pour rappeler aux moins attentifs de l'assistance que votre serviteur est avant toute chose ce qu'il convient d'appeller un "computer geek"? Mais bon, ne parlons pas d'informatique trop sérieuse quand même, ça s'écarterait du sujet ;-)

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'algorithme 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?

Tags:

cc-by-nc | code (python)