Utilisateur:Niniryoku/TriABulle

Pseudo code représenté par cet image

maximum = longeur(tableau)
tant que maximum est supérieur à 0
    maximumTemporaire = 0
    pour i de 1 à maximum
        si la valeur à la position i-1 de tableau
           est supérieure à
           la valeur à la position i   de tableau:
              inverserLesValeursDesPositions(tableau, i, i-1)
              maximumTemporaire = i
    maximum = maximumTemporaire

Algorithme pour générer l'image

Création des fichiers

touch tri.py
mkdir im

tri.py

#!/usr/bin/python
# -*- coding: utf-8 -*-
# (c) 2009, Niniryoku

import random
import Image

def genTableauAlea(n):
    # Génération d'une graine aléatoire
    random.seed(None)

    # Listes
    listeNb = range(n)
    res     = []

    # Génération de la liste (res) contenant la suite de nombre
    # de 0 à n - 1 dans le désordre
    while listeNb:
        alea = random.choice(listeNb)
        res.append(alea)
        listeNb.remove(alea)
    return res

# Maxi est propre à cet algorithme, il peut être retiré
def image(liste, n, ratio, maxi):
    # Si vous n'avez pas besoin de maxi, mettez comme extension bmp
    #         'im/tab-%02d.bmp'
    fichier = 'im/tab-%02d.gif' % n
    taille = len(liste)
    tmp    = taille - 1
    # Si vous n'avez pas besoin de maxi, l'image n'utilise que deux couleurs
    # Utilisez donc :
    #     Image.new('1', (taille * ratio, taille * ratio), 1)
    img = Image.new('RGB', (taille * ratio, taille * ratio), (255, 255, 255))
    for i in range(taille):
        # Retirez les quatre lignes suivantes si vous n'utilisez pas maxi
        if i == maxi:
            couleur = (255, 0, 0)
        else:
            couleur = (0, 0, 0)

        # Localisation du pixel à modifié
        x = liste[i] * ratio
        y = (tmp - i) * ratio
        # Taille du pixel selon le ratio
        for j in range(ratio):
            for k in range(ratio):
                # Si vous n'utilisez pas maxi, remplacez cette ligne par :
                #     img.putpixel((x + j, y + k), 0)
                img.putpixel((x + j, y + k), couleur)

    # Retirez cette ligne si vous n'utilisez pas maxi
    img.convert('P')
    # Si vous n'avez pas besoin de maxi, remplacez cette ligne par
    #     img.save(fichier, 'BMP')
    img.save(fichier, 'GIF')

taille = input('Entrez la taille du tableau : ')
tab = genTableauAlea(taille)
ratio = input('Entrez le ratio : ')

# Algorithme de tri
# modifiez ce code pour générer une image animée
# d'un autre algorithme de tri
maxi = taille
compt = 0
image(tab, compt, ratio, maxi - 1)
while maxi > 0:
    tmpmax = 0
    compt += 1
    for i in range(1, maxi):
        if tab[i-1] > tab[i]:
            tab[i], tab[i-1] = tab[i-1], tab[i]
            tmpmax = i
    # Création d'une image, il est important de maintenir un compteur
    image(tab, compt, ratio, maxi)
    maxi = tmpmax

License

Copyright © 2009, Niniryoku All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

• Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
• Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
• Neither the name of the Niniryoku nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Génération du gif animé

python tri.py
# Pour mon image : 100 et 4
cd im/
convert -delay 10 -loop 0 \
        -comment "(CC-BY 3.0) Niniryoku\nhttp://fr.wikipedia.org/wiki/Utilisateur:Niniryoku" \
        tab-*.gif tabAnim.gif

Si vous n'utilisez pas la variable maxi, vos images sont en bmp. Utilisez donc tab-*.bmp à la place de tab-*.gif. tabAnim.gif ne change pas.

tabAnim.gif contient le gif animé de l'algorithme de tri.