Forum de mathématiques - Bibm@th.net

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri

Salut,

En ce qui concerne le code Python de Batcher odd-even MergeSort, il est hélas incorrect : il permet de calculer des indices hors-limites et paf plantage ! Là,  je ne suis pas en cause, j'ai fait un copier/coller et lancé le truc...
J'ai donc trouvé où ça cloche, j'ai fait une correction à l'arrache : il fonctionne...
Mais le correctif n'est pas rationnel puisque je permets toujours le dépassement mais que, par traitement d'erreur, j'intercepte ladite erreur quand elle se produit.
Mais je pense avoir compris comment modifier : je m'y attelle demain...

Oh, je ne suis pas spécialiste non plus : j'ai la sensation que tri de Batcher ou de Bose-Nelson sont très voisins, exploitant le même principe d'écart maximum qu'on divise régulièrement par 2...

Ah... (illumination) mais quand j'ai dit "incorrectement qualifié de tri de Batcher", je ne pensais pas à toi bien sûr, mais aux deux seuls sites en français qui en parlent, dont l'un est fortement inspiré de l'autre...
Rassuré ? ;-)

@+

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri

Bonjour,

Les nuées semblent se dissiper...
En effet, Batcher a découvert deux méthodes de tri :
- Le tri en parallèle ajouté la dernière fois,
- Le tri "oddeven merge sort", qu'on pourrait traduire par "Tri de fusion PairImpair".
  Ce tri ne fonctionne qu'avec un nombre d'éléments qui est une puissance de 2 :
  En voici le code :
 

def oddeven_merge_sort(n,x):
    oddeven_merge_sort_range(x, 0, n-1)
    return x
 
def oddeven_merge_sort_range(x, lo, hi):
    """ Trie la partie de x d'indices compris entre lo et hi
        Note : Les bornes (lo et hi) sont incluses.
    """
    if (hi - lo) >= 1:
    # s'il y a plus d'un élément, partage la partie passée en paramètre
    # en descendant jusqu'au milieu, trie d'abord la première et la 2nde moitié
    # puis les fusionne.  
        mid = lo + ((hi - lo) // 2)
        oddeven_merge_sort_range(x, lo, mid)
        oddeven_merge_sort_range(x, mid + 1, hi)
        oddeven_merge(x, lo, hi, 1)

def oddeven_merge(x, lo, hi, r):
    step = r * 2
    if step < hi - lo:
        oddeven_merge(x, lo, hi, step)
        oddeven_merge(x, lo + r, hi, step)
        for i in range(lo + r, hi - r, step):
            compare_and_swap(x, i, i + r)
    else:
        compare_and_swap(x, lo, lo + r)

def compare_and_swap(x, a, b):
    if x[a] > x[b]:
        x[a], x[b] = x[b], x[a]

Je n'ai pas trouvé tout seul la spécification "puissance de 2", j'aurais dû mais j'ai négligé la précision en anglais.
Il y a un moyen de contourner l'obstacle, si la taille du tableau n'est trop inférieure à une puissance de 2 :
rajouter assez d'éléments dans le tableau, pour les supprimer après tri.
Lesquels ?
Il m'a été suggéré d'ajouter None autant de fois que nécessaire, None étant considéré comme inférieur à n'importe quel nombre...
J'avais modifié l'algo autrement, mais il m'a été fait remarquer que le Tri était alors incorrect.
Donc pour l'ajout, on intervient ici :

def oddeven_merge_sort(n,x):
    #ajout du nombre voulu de None
    cor = 2**(int(ceil(log(n, 2))) ) - n
    x,n=[None]*cor+x,n+cor
    # inchangé
    oddeven_merge_sort_range(x, 0, n-1)
    # suppression des None
    while x[0]==None:
        del x[0]
    return x

J'ai testé cette version pour n=2048, 4096,8192 :
Moyenne des temps :

         Nombres à trier     2048    |    4096     |   8192  
                           ----------|-------------|---------
                                          Temps  
                          -----------|-------------|---------
Tri dichotomique         : 0.215 s   |   0.731 s   |  2.997 s
Tri par Insertion        : 0.412 s   |   1.581 s   |   6.122 s
Tri à bulles             : 1.172 s   |   4.341 s   |  17.634 s
Tri de Shell-Metzner     : 0.016 s   |   0.041 s   |   0.088 s
Tri rapide               : 0.001 s   |   0.015 s   |   0.031 s
Tri de fusion            : 0.001 s   |   0.028 s   |   0.053 s
Tri par casiers          : 0.003 s   |   0.003 s   |   0.000 s
Tri par tas              : 0.025 s   |   0.031 s   |   0.072 s
Tri radix                : 0.028 s   |   0.037 s   |   0.112 s
Tri de Batcher  //       : 0.028 s   |   0.088 s   |   0.209 s
Tri de fusion de Batcher : 0.053 s   |   0.112 s   |   0.347 s

J'ai également trouvé une autre version du tri parallèle de Batcher, en Javascript cette fois, que j'ai adaptée en Python :

def Batcher(n,L):
    exp=int(ceil(log(n,2)))
    fin=2*exp+1
    for p in reversed(xrange(1,fin)):
        r,d=0,p
        for q in reversed(xrange(p,fin)):
            for k in xrange(n-d):
                if ((k-1)and p)==r:
                    if L[k]>L[k+d]:
                        L[k],L[k+d]=L[k+d],L[k]
            d,r=q-p,p
    return L

Elle est plus compacte que celle mise en ligne, mais aussi.... 2 fois plus lente !

Et pour voir, m'étant souvenu que j'avais utilisé de par le passé le module psyco pour python (pour version de Python jusqu'à 2.6.x), j'ai refait un test avec 16384 nombres...
Voilà l'effet de psyco (moyennes de 5 tests également) :

Nombres à trier           | 16384 |  
                          ---------
                            Temps  
                          ---------
Tri dichotomique         : 1.803 s
Tri par Insertion        : 1.369 s
Tri à bulles             : 5.834 s
Tri de Shell-Metzner     : 0.016 s
Tri rapide               : 0.006 s
Tri de fusion            : 0.037 s
Tri par casiers          : 0.006 s
Tri par tas              : 0.016 s
Tri radix                : 0.069 s
Tri de Batcher  //       : 0.037 s
Tri de fusion de Batcher : 0.131 s

Impressionnant, l'efficacité du module psyco !
Dommage qu'il ne soit pas encore maintenu pour les versions de Python >=2.7

@+

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri

Bonjour,

En fouillant les sites américains; j'ai fini par avoir une certitude...
J'avais tort.
Batcher est l'inventeur de 2 méthodes de tri :
- Bitonic sort
- oddeven merge sort.
Le tri bitonique est appelé ainsi par opposition à d'autres tri qui sont monotoniques, de l"adjectif monotone pris dans son sens mathématique : fonction monotone croissante (ou décroissante) :

Knuth, sorting and searching, p 232]
   " Let us say that a sequence ⟨[tex]z_1,\cdots z_p[/tex]⟩ of p numbers is bitonic if [tex]z_1 \geq \cdots \geq z_k \leq \cdots \leq z_p[/tex] for some k, 1 ≤ k ≤ p […]
A bitonic sorter of order p is a comparator network capable of sorting any bitonic sequence of length p into non-decreasing order […] [W]e can construct a bitonic sorter of order p […] by first sorting the bitonic subsequences [tex]z_1,\, z_3,\, z_5[/tex] ... and [tex]z_2,\, z_4,\, z_6[/tex], …⟩ independently, then comparing and interchanging z1:z2, z3:z4, …"

Le "oddeven merging sort" ne fonctionne que pour des tailles de liste égales à une puissance de 2. Je l'ai adapté pour qu'il ajuste automatiquement le nombre d'éléments en rajoutant les éléments None en quantité nécessaire et en les supprimant en fin de tri, de façon transparente.
Il est bien évident que si la taille est déjà une une puissance de 2, la modif ajoutera 0 (zéro) élément None supplémentaire.
Moyennant quoi, ce tri fonctionne très bien quelle que soit la taille, sauf que si je demande un tri de 10 000 nombres, il va ajouter 6 384 éléments None supplémentaires pour les retirer après, ce qui risque fort d'en pénaliser la performance.
J'ai donc inclus ce tri dans mon programme de test.

#!/usr/bin/env python
# -*- coding: cp1252 -*-

from __future__ import division
from time import time
from math import log,ceil

def sortie():
    print
    print
    print "                       Au revoir !"

def commente(chx):
    if chx==4:
        print "   Méthode faisant appel à la récursivité, donc un plus gourmande en mémoire."
        print "Elle consite à trier tous les éléments d'une liste par rapport à un autre, le"
        print "pivot, arbitrairement choisi et de grouper ceux qui lui sont inférieurs avant"
        print "(tri croissant) et les autres après."
        print "Puis on reprend chaque partie, en modifiant les bornes et on recommence."
        print

def tri_insertion(n,L):
    print "   Le tri par insertion est un tri simple, proche du tri à bulles."
    print "Insérer un nombre dans la portion de liste qui le précède et supposée"
    print "triée, demande qu'on le compare de proche en proche à chacun de ceux"
    print "le précèdent, jusqu'à ce qu'on trouve son emplacement."
    print "On décale alors les nombres examinés pour pouvoir le mettre en place,"
    print "l'insérer, d'où le nom."
    print "Comme la liste de départ n'est pas censée être déjà triée, on commence"
    print "par comparer le 2e nombre de la liste avec le 1er : ce 1er nombre cons-"
    print "titue bien une liste triée... Le nombre une fois inséré, nous disposons"
    print "nous disposons d'une liste triée à 2 éléments."
    print "Il est alors temps d'insérer le 3e nombre dans cette liste à 2 éléments,"
    print "et ainsi de suite, jusqu'à terminer par l'insertion du n-ième élément"
    print "dans une liste triée de n-1 éléments."
    print    
    for i in xrange(1,n):
        nb,j=L[i],i
        while L[j - 1] > nb and j > 0:
            L[j],j = L[j - 1],j-1
        L[j] = nb
    return L
     
 
def bulle(n,L):
    print "   Le tri à bulles est parmi les plus simples mais aussi les plus lents."
    print "Chaque élément est comparé à celui qui le suit, d'où la double boucle."
    print "S'il lui est supérieur (tri croissant), on les intervertit."
    print
    change=1
    while change:
        change=0
        for i in xrange(n-1):
            if L[i]>L[i+1]:
                L[i],L[i+1]=L[i+1],L[i]
                change = 1
    return L

def metzner(n,L):
    print "   Le tri de Shell-Metzner a pour intérêt sa faible gourmandise en ressources."
    print "Dérivé du tri à bulles, au lieu de comparer un élément à ses voisins immédiats,"
    print "on compare des éléments distants ; la distance maxi est obtenue à partir de la"
    print "suite U(n+1)= 3*U(n)+1 avec U(0)=0. On peut remplacer 3 par 2, ce qui permet de"
    print 'retomber sur la méthode "courante".'
    print "Comme pour le tri à bulle, on répète un balayage complet jusqu'à ce qu'aucun"
    print "élément soit échangé. On passe à l'incrément suivant, qui est plus petit que le"
    print "précédent, et on reprend les balayages."
    print "Le tri prend fin lorsque qu'aucun élément du tableau n'a été échangé et que la"
    print "taille de l'incrément (la variable pas) est 1."
    print
    while pas <n:
        pas=3*pas+1       # <--|  
    while pas >0:         #    | on peut remplacer 3 par 2
        pas //=3          # <--|
        for i in xrange(pas,n):
            j,trsf=i,L[i]
            while (j>pas-1) and (L[j-pas]>trsf):
                L[j]=L[j-pas]
                j-=pas
            L[j]=trsf
    return L                                                                

def dicho(n,L):
    print "    Le principe du tri dichotomique est assez simple : le i-ème de la liste"
    print "est comparé à tous ceux qui le précèdent dans cette liste."
    print "On cherche alors la place qu'il devrait occuper et on décale tous les élé-"
    print "ments. Cette opération est renouvelée pour chaque élément de la postion 2 à"
    print "la position n."
    print
    for i in xrange(1,n):
        if L[i]<L[i-1]:
            if L[i]>L[0]:
                pos=placement(i,L)
            else:
                pos=0
            trsf=L[i]
            for j in reversed(xrange(pos+1,i+1)):
                L[j]=L[j-1]
            L[pos]=trsf
    return L  

def placement(i,L):
    mini,maxi=0,i
    while mini != maxi:
        ml=(mini+maxi)//2
        if L[i]<L[ml]:
            maxi=ml
        elif L[i]>L[ml]:
            mini=ml+1
    return mini

def quick(db,fin,L):
    pivot=L[(db+fin)//2]
    i,j=db,fin-1
    while 1:
        while L[i]<pivot:
            i+=1
        while pivot<L[j]:
            j-=1
        if i<=j:
           L[i],L[j]=L[j],L[i]
           i+=1
           j-=1
        if i>j:
            break
    if db<j:
        quick(db,j,L)
    if i<fin:
        quick(i,fin,L)
    return L

def tri_fusion(n,L):
    print "   Le principe du tri de fusion est la décompositionr la liste à trier"
    print "en sous-listes de plus en plus petites d'une longueur 2 ou 1, pour les"
    print "ordonner. Ceci fait, on fusionne ces fichiers ordonnés 2 à 2, jusqu'à"
    print "de la liste totalement ordonnée"
    print
    l=n-n%2
    S1,S2,S=[],[],[]
    for i in xrange(0,l,2):
        if L[i]>L[i+1]:
            S.append([L[i+1],L[i]])
        else:
            S.append([L[i],L[i+1]])
    if n%2:
        S.append([L[l]])
    long,p=len(S),len(S)%2
    T,S=S[:],[]
    while not long<2:
        for i in xrange(0,long-p,2):
            S.append(fusionner(T[i],T[i+1]))
        if long%2:
            S+=T[-1:]
        long,p=len(S),len(S)%2
        T,S=S[:],[]
    return T[0]

def fusionner(S1,S2):
    n1,n2,n=len(S1),len(S2),len(S1)+len(S2)
    L=[0]*n
    i,j,k=0,0,0
    while i<n1 or j<n2:
        if j>=n2:
            L[k]=S1[i]
            i+=1
        elif i>=n1:
            L[k]=S2[j]
            j+=1
        elif S1[i]<=S2[j]:
            L[k]=S1[i]
            i+=1
        else:
            L[k]=S2[j]
            j+=1
        k+=1
    return L

def casiers(n,L):
    print "   Le tri par casiers souffre d'une limitation : il ne fonctionne que sur"
    print "une liste de nombres entiers."
    print "Il nécessite de trouver le plus grand élément (sup) présent dans la liste"
    print "pour initialiser une liste de comptage (des casiers) de (sup+1) zéros."
    print "On parcourt ensuite n un par un, tous les index des éléments de la liste"
    print "à trier et on incrémente à chaque fois de 1 la valeur du casier dont le"
    print "numéro d'ordre est le nombre de la liste à trier correspondant à l'index"
    print "courant."
    print "Il n'y a plus alors qu'à passer en revue chacun des casiers précédents, le"
    print "numéro d'ordre, si le casier contient autre chose que zéro, est un nombre"
    print "de la liste initiale, la valeur étant le nombre fois qu'il est présent."
    print "   Toutefois, si l'on voulait trier autre chose que des entiers il reste"
    print "possible de contourner la difficulté en créant une liste référençant ces"
    print "objets."
    print
    sup=max(L)
    casier=[0]*(sup+1)
    for nb in L:
        casier[nb]+=1
    k=0
    for i in xrange(sup+1):
        if casier[i]>0:
            for j in xrange(casier[i]):
                if casier[i]>0:
                    L[k]=i
                    k+=1
    return L

def tri_par_tas(n,L):
    print "   Le principe de base du tri par tas est de considérer la liste à"
    print "comme un arbre vertical, mais binaire : chaque branche se subdivi-"
    print" sant en 2."
    print "Dans la liste fournie, 51 est la racine, 31 et 1 sont ses enfants,"
    print "44 et 42 sont les enfants de 31 etc... Les 2 descendants d'un élé-"
    print "ment i ont pour index 2i et 2i+1 pour une liste d'indice initial 1."
    print "Si i>0 alors i est à la fois fils et parent, c'est un noeud."
    print "Le principe du tri est de réaliser un 'tas' mathématique :"
    print "* Pour un tri croissant, chaque noeud doit être de valeur inférieure"
    print "  à chacun de ses fils et supérieure à celle de son parent,"
    print "* Au bout de chaque branche, se trouve une feuille. Toutes les"
    print "  feuilles doivent se trouver sur la dernière ou l'avant-dernière"
    print "  ligne,"
    print "* les ramifications doivent être réorganisées de façon que les"
    print "  feuilles les plus éloignées de la racine se trouvent toutes à"
    print "  gauche, sur la dernière ligne."
    print
    for i in reversed(xrange(n//2)):
        L=fait_tas(i,n,L)
    for i in reversed(xrange(1,n)):
        L[0],L[i]=L[i],L[0]      
        L=fait_tas(0,i-1,L)
    return L

def fait_tas(i,n,L):
    p=i
    j=2*p
    while j<n:
        if j<=n and L[j]<L[j+1]:
            j+=1
        if L[p]<L[j]:
            L[p],L[j]=L[j],L[p]
            p=j
            j=2*p
        else:
            break
    return L

def radix(n,L):
    print"   Le tri par base est très rapide, il est limité ici à des nombres entiers"
    print "naturels. On pourrait cependant l'adapter pour trier des décimaux relatifs,"
    print "voire des mots."
    print "Il nécessite de disposer des valeurs minimum et maximum de la liste à trier."
    print "Après quoi, on procédera aux tris successifs selon les unités, les dizaines,"
    print "les centaines, etc..."
    print "La seule contrainte étant de laisser dans l'ordre de la liste d'origine, les"
    print "nombres ayant la mêne unité, puis dizaine, centaine, etc..."
    print
    S=[]
    mini,maxi=len(str(min(L)))-1,len(str(max(L)))
    for i in xrange(mini,maxi):
        for j in xrange(0,10):
            for nb in L:
                if (nb//10**i)%10==j:
                    S.append(nb)
        L,S=S[:],[]
    return L

def Batcher_bitonic(n,L):
    print "   Le tri de Bose-Nelson n'est pas évident à mettre en oeuvre."
    print "Il nécessite de calculer l'écart maximum entre deux éléments d'une"
    print "liste, en trouvant l'exposant maximum x tel que 2^x >= taille de la"
    print "liste, cet écart valant 2^(x-1)."
    print "Il faut ensuite Comparer/échanger deux par deux, tous les éléments"
    print "de la liste distants respectivement de 2^(x-1), 2^(x-2)... 1."
    print " Ce rôle est dévolu au test binaire : if (i and p) == r ..."
    x = int(ceil(log(n,2)))
    p,ecart_max = 2**x,2**(x-1)
    while p >= 2:
        p = p// 2
        q = ecart_max
        r = 0
        d = p
        fin = 0
        while not fin :
            for i in xrange(0,n-d):
                if (i and p) == r :
                    if L[i] > L[i+d]:
                        L[i],L[i+d] = L[i+d],L[i]
            if q <> p:
                d = q - p
                q = q//2
                r = p
                fin = 0
            else:
                fin = 1
    return L

def oddeven_merge_sort(n,x):
    #ajout du nombre voulu de None
    cor = 2**(int(ceil(log(n, 2))) ) - n
    x,n=[None]*cor+x,n+cor
    # inchangé
    oddeven_merge_sort_range(x, 0, n-1)
    # suppression des None
    while x[0]==None:
        del x[0]
    return x
 
def oddeven_merge_sort_range(x, lo, hi):
    """ Trie la partie de x d'indices compris entre lo et hi
        Note : Les bornes (lo et hi) sont incluses.
    """
    if (hi - lo) >= 1:
    # s'il y a plus d'un élément, partage la partie passée en paramètre
    # en descendant jusqu'au milieu, trie d'abord la première et la 2nde moitié
    # puis les fusionne.  
        mid = lo + ((hi - lo) // 2)
        oddeven_merge_sort_range(x, lo, mid)
        oddeven_merge_sort_range(x, mid + 1, hi)
        oddeven_merge(x, lo, hi, 1)

def oddeven_merge(x, lo, hi, r):
    step = r * 2
    if step < hi - lo:
        oddeven_merge(x, lo, hi, step)
        oddeven_merge(x, lo + r, hi, step)
        for i in range(lo + r, hi - r, step):
            compare_and_swap(x, i, i + r)
    else:
        compare_and_swap(x, lo, lo + r)

def compare_and_swap(x, a, b):
    if x[a] > x[b]:
        x[a], x[b] = x[b], x[a]

L=[103,51,31,1,44,42,39,48,52,26,38,53,4,57,3,45,20,27,25,30,15,37,12,46,13,47,\
    6,54,17,18,2,24,23,22,21,19,29,56,10,5,7,58,59,33,1037,34,28,14,235,11,43,16,\
    55,32,9,8,60,36,35,41,49]
n=len(L)
Menu={1:"Tri dichotomique",2:"Tri par Insertion",3:"Tri à bulles",\
      4:"Tri de Shell-Metzner",5:"Tri rapide (Quick Sort)",6:"Tri de fusion",\
      7:"Tri par casiers",8:"Tri par tas",9:"Tri radix (ou tri par base}",\
      10:"Tri de Batcher bitonique",11:"Tri de fusion de Batcher"}
dico={1:dicho,2:tri_insertion,3:bulle,4:metzner,5:quick,6:tri_fusion,7:casiers,\
      8:tri_par_tas,9:radix,10:Batcher_bitonic,11:oddeven_merge_sort}
while 1:
    aa = 1
    while aa == 1:
        try:
            print "          ***********************"
            print "          * Algorithmes de tris *"
            print "          *       v. 3.5        *"
            print "          ***********************"
            print
            print
            for i in xrange(1,12):
                print "%2i" % i,"-",Menu[i]
            print
            print "      0 - Arrêt du programme"
            print
            chx = int(raw_input("Votre choix : "))
            if chx > 11 or chx < 0:
                print
                print "Désolé ! Vous n'avez pas entré un nombre valide. Veuillez recommencer..."
                print
                print
            else:
                break
        except ValueError:
            print
            print "Désolé ! Ce n'est pas un nombre. Essayez encore..."
            print
            print
    if chx == 0:
        sortie()
        break
    else:
        print
        print
        print "Liste avant tri :"
        print L
        print
        print "Liste triée, méthode du",Menu[chx]
        print
        if chx == 5:
            M=dico[chx](0,n,L)
        else:
            M=dico[chx](n,L)
        print
        print M
        print
   
    raw_input('       ... Presser Entrée pour retourner au menu ...')
    print
    print

A cette occasion, j'ai découvert de nombreuses autres méthodes de tri que je vais m'empresser de tester et rajouterais éventuellement selon l'originalité et/ou la rapidité...

@+

-- Edit Fred : j'ai juste modifié la balise code pour voir la coloration syntaxique sous Python...

Dernière modification par Fred (19-07-2011 21:50:46)

alcinos

Invité

Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri

Salut,

J'apporte ma modeste contribution au sujet : il est possible d'améliorer légèrement la procédure casiers pour éviter l'imbrication des boucles for, et ainsi se retrouver avec une vraie complexité linéaire (dans le code actuel, dans un cas défavorable où la liste contient des éléments tous égaux, l'algo exécute n*n opérations)

def casiers2(n,L):
    print "   Le tri par casiers souffre d'une limitation : il ne fonctionne que sur"
    print "une liste de nombres entiers."
    print "Il nécessite de trouver le plus grand élément (sup) présent dans la liste"
    print "pour initialiser une liste de comptage (des casiers) de (sup+1) zéros."
    print "On parcourt ensuite n un par un, tous les index des éléments de la liste"
    print "à trier et on incrémente à chaque fois de 1 la valeur du casier dont le"
    print "numéro d'ordre est le nombre de la liste à trier correspondant à l'index"
    print "courant."
    print "Il n'y a plus alors qu'à passer en revue chacun des casiers précédents, le"
    print "numéro d'ordre, si le casier contient autre chose que zéro, est un nombre"
    print "de la liste initiale, la valeur étant le nombre fois qu'il est présent."
    print "   Toutefois, si l'on voulait trier autre chose que des entiers il reste"
    print "possible de contourner la difficulté en créant une liste référençant ces"
    print "objets."
    print
    sup=max(L)
    M=[0]*len(L)
    casier=[0]*(sup+1)
    for nb in L:
        casier[nb]+=1
    for i in xrange(sup):
        casier[i+1]+=casier[i]
     
    for nb in L:
        M[casier[nb]-1]=nb
        casier[nb]-=1
    return M  

A+

Milos

Membre

Inscription : 11-07-2013

Messages : 94

Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri

Bonsoir à tous,

J'ai déjà dit deux fois que je suis tout nouveau, et je le répète ici pour mon troisième post..

Je suis vraiment content de lire ici des posts qui étaient d'intérêt il y a plus de 30 ans de ca, quand on trouvait en kiosque Ordi PC ou Pascalissime, avec des programmes, des algorithmes comparés, etc.. J'ai commencé en 81 avec un TRS, poursuivi avec un Apple II avec carte CP/M, un PC, un compatible PC, ..
A l'époque on pouvait contrôler les circuits directement, avec des OS actuels on doit s'en remettre aux API; sans parler des difficultés notables, le temps réel devient utopique..
Si je ne vous ennuie pas, je reviendrai sans doute avec un problème d'affichage vidéo en synchronisation avec le rafraîchissement, pour un programme écrit en Pascal.

Je ne connais pas les noms de certains algorithmes que vous citez : tas, casiers, les 4 derniers en fait.

A mon époque, il y avait 2 critères de choix d'un tri (3 avec la mémoire):
- la rapidité
- la stabilité (un tri stable est un tri où, quand on rentre deux éléments de même valeur, ils ressortent dans le même ordre qu'à l'entrée).

Le + rapide théoriquement était et est toujours je pense le quick sort. Sa vitesse est de l'ordre de log2(n), mais pour en bénéficier il y a 2 conditions:
- que le quick sort soit implémenté de façon itérative et pas récursive (on peut démontrer paraît-il que tout algorithme récursif peut être réécrit sous forme itérative, et les sources itératives doivent encore se trouver);
- que l'arbre binaire soit équilibré en temps réel lors du tri (si par malchance l'arbre est déjà quasi-trié dans le mauvais sens, l'arbre au lieu d'avoir une hauteur de log2(n) aura une hauteur de n, avec un temps de parcours maximal), cet équilibrage en temps réel fait écrire beaucoup de lignes, ce qui fait perdre du temps à l'écriture mais surtout perdre du temps si justement la liste est pré triée, lors des échanges de nœuds.
Quand la liste à trier n'est pas triée du tout, c'est vraiment optimal.

Je préférais souvent le Shell-Metzner du coup, qui en 10-20 lignes faisait quasiment aussi bien.
Mais ce tri là est instable (ce qu'on peut toujours contourner par une première boucle en ajoutant un champ d'ordre de liste).

J'espère ne pas vous avoir ennuyé par mes souvenirs d'ancien combattant.

Mais je suis vraiment content de lire un forum où on parle vraiment d'algorithmes et de programmation, ce qui ne m'était pas arrivé depuis des années..

Toutes mes amitiés, en espérant ne pas avoir abusé de votre temps,

Milos.