Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 28-06-2011 10:50:00
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
[Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Bonjour,
ngatilio m'a donné l'idée de regrouper ici différents algos de tri en différents langages.
Je commence en Python (v.2.7) par le "tri à bulles" et le tri de Shell-Metzner :
J'ai l'intention d'ajouter le tri par dichotomie, le Quick sort (tri rapide), le tri par fusion et une interface vous laissant le choix du tri...
# -*- coding: cp1252 -*-
from __future__ import division
def bulle(n,L):
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):
pas=0
while pas <n:
pas=2*pas+1 # <--|
while pas >0: # | on peut remplacer 2 par 3
pas //=2 # <--|
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
L=[31,1,39,40,26,38,3,20,27,25,27,15,37,12,13,6,4,17,18,2,24,23,22,21,19,29,10,5,7,33,34,28,14,11,16,30,9,8,36,35]
n=len(L)
print "Liste avant tri :"
print L
L=metzner(n,L)
print
print "Liste après :"
print L
@+
Hors ligne
#2 28-06-2011 19:41:12
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Suite :
Interface non vérifiée encore.
Je compte ajouter d'autres tris...
# -*- coding: cp1252 -*-
from __future__ import division
def sortie():
print
print
print " Au revoir !"
return
def bulle(n,L):
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):
pas=0
while pas <n:
pas=2*pas+1 # <--|
while pas >0: # | on peut remplacer 2 par 3
pas //=2 # <--|
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):
for i in xrange(1,3):
if L[i]<=L[i-1]:
if L[i]>L[0]:
pos=placement(i,L)
else:
pos=0
trsf=L[i]
for j in xrange(i,pos+1,-1):
L[j]=L[j-1]
L[pos]=trsf
return L
def placement(i,L):
mini,maxi=0,i
while mini != maxi:
ctrl=(mini+maxi)//2
print ctrl,mini,maxi,i
if L[i]<=L[ctrl]:
mini=ctrl+1
else:
maxi=ctrl
place=mini
return place
def quick(n,L):
i,j=0,n-1
ctrl=L[(i+j)//2]
while 1:
while L[i]<ctrl:
i+=1
while ctrl<L[j]:
j-=1
if i<=j:
L[i],L[j]=L[j],L[i]
i+=1
j-=1
if i>j:
break
return L
L=[31,1,39,40,26,38,3,20,27,25,27,15,37,12,13,6,4,17,18,2,24,23,22,21,19,29,10,5,7,33,34,28,14,11,16,30,9,8,36,35]
n=len(L)
Menu={1:"tri dichotomique",2:"tri à bulles",3:"tri rapide (Quick Sort)",\
4:"tri de schell-Metzner"}
while 1:
aa = 1
while aa == 1:
try:
print " ***********************"
print " * Algorithmes de tris *"
print " ***********************"
print
print
print "1 - tri dichotomique"
print "2 - tri à bulles"
print "3 - tri rapide (Quick Sort)"
print "4 - tri de schell-Metzner"
print " 0 - Arrêt du programme"
chx = int(raw_input("Votre choix : "))
if chx > 4 or chx < 0:
print "Désolé ! Vous n'avez pas entré un nombre valide. Veuillez recommencer..."
print
print
else:
break
except ValueError:
print "Désolé ! Ce n'est pas un nombre. Essayez encore..."
print
print
if chx == 0:
sortie()
break
else:
print "Liste avant tri :"
print M
print
print "Liste triée, méthode du",Menu[chx]
if chx==1:
M =dicho(n,L)
print M
print
elif chx==2:
M=bulle(n,L)
print M
print
elif chx==3:
M=quick(n,L)
print M
print
else:
M=metzner(n,L)
print M
print
raw_input(' ... Presser Entrée pour Quitter ...')
print
@+
Hors ligne
#3 29-06-2011 13:17:18
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Mise à jour.
Correction du bug pour Quick sort.
Ajout d'explications.
Interface contrôlée.
Utilisation d'un dictionnaire de fonctions éliminant la suite de if/elif/else...
# -*- coding: cp1252 -*-
from __future__ import division
def sortie():
print
print
print " Au revoir !"
return
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."
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."
pas=0
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."
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 xrange(i,pos+1,-1):
L[j]=L[j-1]
L[pos]=trsf
return L
def placement(i,L):
mini,maxi=0,i
while mini != maxi:
ctrl=(mini+maxi)//2
print ctrl,mini,maxi,i
if L[i]<=L[ctrl]:
mini=ctrl+1
else:
maxi=ctrl
place=mini
return place
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
L=[31,1,39,40,26,38,3,20,27,25,27,15,37,12,13,6,4,17,18,2,24,23,22,21,19,29,10,5,7,33,34,28,14,11,16,30,9,8,36,35]
n=len(L)
Menu={1:"Tri dichotomique",2:"Tri à bulles",3:"Tri de Shell-Metzner",\
4:"Tri rapide (Quick Sort)"}
dico={1:dicho,2:bulle,3:metzner,4:quick}
while 1:
aa = 1
while aa == 1:
try:
print " ***********************"
print " * Algorithmes de tris *"
print " ***********************"
print
print
print "1 - Ttri dichotomique"
print "2 - Tri à bulles"
print "3 - Tri de Shell-Metzner"
print "4 - Tri rapide (Quick Sort)"
print
print " 0 - Arrêt du programme"
print
chx = int(raw_input("Votre choix : "))
if chx > 4 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 "Liste avant tri :"
print L
print
print "Liste triée, méthode du",Menu[chx]
print
if chx==4:
print "Méthode faisant appel à la récursivité, donc un plus consommatrice de 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
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
Maintenant, je vais m'attacher à compléter avec d'autres méthodes.
@+
Hors ligne
#4 30-06-2011 11:26:53
- totomm
- Invité
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Bonjour,
Très sympathique cette idée de regrouper...
Les tris sont parmi les algorithmes les plus importants quand à leur répercusions dans les traitements informatiques.
Mais dans un ouvrage comme celui de Sedgewick, pourtant général sur les algorithmes, il y en a déjà plus de 100 pages. et bien sûr, un bon choix dépend toujours du type de données et du volume de traitement...
Et les algorithmes performants deviennent délicats à comprendre et surtout à bien tester...
Bon accomplissement car apparemment le courage ne manque pas. Cordialement.
#5 30-06-2011 17:34:48
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Salut totomm,
J'en ai bavé avec le tri de fusion.
Toutes les versions récursives trouvées sur Internet et que j'ai adaptées en Python, ne fonctionnent pas, que ce soit depuis le Pascal, Java, C,C++, pseudo-code...
Probablement que mes adaptations étaient mauvaises...
Caml et Lisp : je n'ai rien compris.
J'en suis donc revenu à une méthode itérative, probablement moins rapide, mais fonctionnelle, de mon cru...
# -*- coding: cp1252 -*-
from __future__ import division
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 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."
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."
pas=0
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."
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 xrange(i,pos+1,-1):
L[j]=L[j-1]
L[pos]=trsf
return L
def placement(i,L):
mini,maxi=0,i
while mini != maxi:
ctrl=(mini+maxi)//2
print ctrl,mini,maxi,i
if L[i]<=L[ctrl]:
mini=ctrl+1
else:
maxi=ctrl
place=mini
return place
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):
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=len(S)-len(S)%2
T,S=S[:],[]
while not long<2:
for i in xrange(0,long,2):
S.append(fusionner(T[i],T[i+1]))
if long%2:
S.append(T[-1:])
long=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."
sup=max(L)
casier=[0]*(sup+1)
print sup,n,casier,len(casier)
for i in xrange(n):
casier[L[i]]=casier[L[i]]+1
k=0
for i in xrange(sup+1):
if casier[i]>0:
for j in xrange(casier[i]):
L[k]=i
k+=1
return L
L=[51,31,1,44,42,39,48,26,38,3,45,20,27,25,30,15,37,12,13,47,6,4,17,18,2,24,23,22,21,19,29,\
10,5,7,33,34,28,14,11,43,16,30,9,8,36,35,41,49]
n=len(L)
Menu={1:"Tri dichotomique",2:"Tri à bulles",3:"Tri de Shell-Metzner",\
4:"Tri rapide (Quick Sort)",5:"Tri de fusion",6:"Tri par casiers"}
dico={1:dicho,2:bulle,3:metzner,4:quick,5:tri_fusion,6:casiers}
while 1:
aa = 1
while aa == 1:
try:
print " ***********************"
print " * Algorithmes de tris *"
print " ***********************"
print
print
for i in xrange(1,7):
print str(i)+" - "+Menu[i]
print
print " 0 - Arrêt du programme"
print
chx = int(raw_input("Votre choix : "))
if chx > 6 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 "Liste avant tri :"
print L
print
print "Liste triée, méthode du",Menu[chx]
print
if chx == 4:
commente(chx)
S=[0]*n
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[
J'ai aussi ajouté le tri par casiers (ou comptage) redoutable pour trier des entiers puisqu'il n'exécute aucune comparaison entre les nombres.
J'ai quand même trouvé un code Python valide dans les tutos de developpez.net pour le tri fusion, mais comme ce n'est pas mon style, je n'ai pas trop cherché à le modifier à ma sauce, ni n'ai voulu fournir une copie (servile) que je n'aurais pas élaborée moi-même...
Ce qui m'a posé problème ce sont les appels récursifs pour découper la liste de départ en 2 parties de longueurs aussi égales que possible, puis de nouveau chaque sous-liste en 2 et ainsi de suite...
La fusion de fichiers de longueurs inégales ne posant pas problème, j'ai donc opté pour le cheminement inverse, en créant des groupes de 2 éléments ordonnés (c'est simple et rapide) et de 1 à la fin en cas de nombre d'éléments impair...
Si quelqu'un peut me fournir une première partie récursive (fonction tri_fusion) appelant ma fonction fusionner, je suis preneur.
Tous les traductions effectuées en Python souffrent du même mal : le découpage ne s'effectue pas et il n'y a pas nulle part d'espace de stockage pour les éléments autres que ceux en cours de traitement...
@+
Hors ligne
#6 02-07-2011 10:26:48
- SébastienB
- Membre
- Lieu : Annecy
- Inscription : 16-06-2008
- Messages : 55
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Salut BibM@th!
Si vous permettez, je souhaite apporter ma modeste contribution à cette intéressante discussion.
Une fois un personnage important a dit que le récursif était élégant.
Aujourd'hui , je me demande comment justifier le choix de ce paradigme, je veux dire de la programmation fonctionnelle ?
LISP est bien expliqué sur cette page web j'ai trouvé :http://www.dontveter.com/basisofai/13.html
L'algorithme QuickSort en LISP ci dessous fonctionne bien:
(setq i '(e iteration))
(defun qs (l)
(let* ((twolists nil)
(left nil)
(right nil)
(sortedleft nil)
(sortedright nil)
)
(cond ((null l) nil)
(t (setq twolists (partition (car l) (cdr l)))
(print iteration)
(print i)
(setq iteration (+ iteration 1))
(setq left (car twolists))
(setq right (cdr twolists))
(setq sortedleft (qs left))
(setq sortedright (qs right))
(append sortedleft
(cons (car l) sortedright))))))
(defun partition (key l) (partition2 key l nil nil))
(defun partition2 (key l left right)
(cond ((null l) (cons left right))
(t (cond ((> (car l) key)
(partition2 key (cdr l) left
(cons (car l) right)))
(t (partition2 key (cdr l)
(cons (car l) left)
right))))))
1
(E ITERATION)
2
(E ITERATION)
3
(E ITERATION)
4
(E ITERATION)
5
(E ITERATION)
6
(E ITERATION)
7
(E ITERATION)
8
(E ITERATION)
9
(E ITERATION)
10
(E ITERATION)
(-1 0 0 0 1 20 43 46 71 88)
Ci dessous, comme souvenance, voici la première version de cet algorithme connu que j'avais codé en C compréhensible:
#include <stdlib.h>
static int compteurPermutation = 0;
void permut(int* i1, int* i2)
{
*i1 = *i1 + *i2;
*i2 = *i1 - *i2;
*i1 = *i1 - *i2;
}
void quicksort (int tableau[], int debut, int fin)
{
int begin = debut;
int end = fin;
int mil = (begin + end ) / 2;
do
{
while ((tableau[begin] < tableau[mil]) && (begin < mil)) begin++;
while ((tableau[end] > tableau[mil]) && (end > mil)) end--;
if ( tableau[begin] > tableau[end] )
{
printf("%d permutation...\n", ++compteurPermutation);
permut (&tableau[begin], &tableau[end]);
}
begin++;
end--;
} while ( begin < end );
if (begin < fin ) quicksort(tableau, begin, fin);
if (end > debut ) quicksort(tableau, debut, end);
}
int main()
{
int i;
int tab[10] ={1};
tab[5] = 88;
tab[6] = 71;
tab[9] = 43;
tab[1] = 20;
tab[2] = 46;
tab[3] = -1;
printf("Affichage du tableau avant le tri:\n");
for ( i = 0; i < 10; i++ )
{
printf("%d ", tab[i] );
}
printf("\n");
quicksort(tab, 0, 9);
printf("Affichage du tableau apres le tri:\n");
for ( i = 0; i < 10; i++ )
{
printf("%d ", tab[i] );
}
return 0;
}
@+
Hors ligne
#7 02-07-2011 10:51:27
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
RE,
Si vous permettez, je souhaite apporter ma modeste contribution à cette intéressante discussion...
Volontiers !
Ce topic est là pour ça...
Je cherche actuellement d'autres méthodes originales, moins connues, et si possible rapides : le bouquin signalé par totomm n'est pas consultable librement, sauf... à le trouver dans une bibliothèque !
J'ai trouvé le tri par tas, encore appelé tri Maximier ou Williams : j'y travaille...
@+
Hors ligne
#8 02-07-2011 11:24:17
- SébastienB
- Membre
- Lieu : Annecy
- Inscription : 16-06-2008
- Messages : 55
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Le spécialiste dont il était question a apparemment mis des liens vers d’intéressants documents depuis sa page web.
Les slides à cette adresse sont super bien je trouve:
http://www.cs.princeton.edu/~rs/AlgsDS07/
Par exemple l'utilisation d'un arbre binaire de recherche me paraît efficace:
http://www.cs.princeton.edu/~rs/AlgsDS0 … hTrees.pdf
J'espère que cela t'aidera à trouver les algorithmes de tri que tu recherches.
@+
Hors ligne
#9 02-07-2011 12:04:35
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Bonjour,
Il y a aussi, ici, un Quicksort et un tri par insertion codés en OCaml : http://sites.google.com/site/theveneau/ … mation.pdf
Hors ligne
#10 02-07-2011 16:47:05
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
RE,
Thadrien, peux-tu ajouter les codes sources dans ce topic, comme Sebastien ? Merci d'avance...Quant à moi, j'ai ajouté le tri par tas...
# -*- coding: cp1252 -*-
from __future__ import division
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 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."
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."
pas=0
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."
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 xrange(i,pos+1,-1):
L[j]=L[j-1]
L[pos]=trsf
return L
def placement(i,L):
mini,maxi=0,i
while mini != maxi:
ctrl=(mini+maxi)//2
print ctrl,mini,maxi,i
if L[i]<=L[ctrl]:
mini=ctrl+1
else:
maxi=ctrl
place=mini
return place
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"
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=len(S)-len(S)%2
T,S=S[:],[]
while not long<2:
for i in xrange(0,long,2):
S.append(fusionner(T[i],T[i+1]))
if long%2:
S.append(T[-1:])
long=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)
casiers=[0]*(sup+1)
for i in xrange(n):
casiers[L[i]]=casiers[L[i]]+1
k=0
for i in xrange(sup+1):
if casiers[i]>0:
for j in xrange(casiers[i]):
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-1 et 2i pour une liste d'indice initial 0."
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
L=[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,33,34,28,14,11,43,16,55,30,9,8,36,35,41,49]
n=len(L)
Menu={1:"Tri dichotomique",2:"Tri à bulles",3:"Tri de Shell-Metzner",\
4:"Tri rapide (Quick Sort)",5:"Tri de fusion",6:"Tri par casiers",\
7:"Tri par tas"}
dico={1:dicho,2:bulle,3:metzner,4:quick,5:tri_fusion,6:casiers,7:tri_par_tas}
while 1:
aa = 1
while aa == 1:
try:
print " ***********************"
print " * Algorithmes de tris *"
print " * v. 3.2 *"
print " ***********************"
print
print
for i in xrange(1,8):
print str(i)+" - "+Menu[i]
print
print " 0 - Arrêt du programme"
print
chx = int(raw_input("Votre choix : "))
if chx > 7 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 "Liste avant tri :"
print L
print
print "Liste triée, méthode du",Menu[chx]
print
if chx == 4:
commente(chx)
S=[0]*n
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
Hors ligne
#11 02-07-2011 18:19:27
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
@yoshi : j'ajoute également les codes sources dans ce topic, néanmoins, je tiens à préciser que la version .pdf a un gros avantage : elle comporte également une coloration syntaxique ! Quand j'avais fait ce document il y a maintenant 3 ans, je me souviens avoir passé du temps pour cela.
Tri par insertion :
(* Profil : 'a list -> 'a list
Terminaison : Longueur de liste decroit dans N
Retourne liste triee par ordre croissant *)
let rec inserer (sliste, elt) =
(* Profil : 'a list * 'a -> 'a list
Terminaison : Longueur de sliste decroit dans N
Insere elt dans sliste en conservant l'ordre
Retourne la liste obtenue *)
match sliste with
|[]
-> [elt]
|hd::tl when hd < elt
-> hd::inserer(tl, elt)
|hd::tl
-> elt::hd::tl
in
match liste with
|[] -> []
|hd::tl -> inserer (tri_insertion(tl), hd)
;;
Tri rapide :
(* Profil : 'a list -> 'a list
Terminaison : Longueur de liste decroit dans N
Retourne liste triee par ordre croissant *)
let rec partition (inf, egal, sup, liste, pivot) =
(* Profil : 'a list * 'a list * 'a list * 'a list * 'a
-> 'a list * 'a list * 'a list
Retourne liste partitionnes en trois :
les elements inferieurs a pivot,
ceux egaux, ceux superieurs *)
match liste with
|[] -> (inf, egal, sup)
|hd::tl ->
if hd < pivot then
partition (hd::inf, egal, sup, tl, pivot)
else if hd = pivot then
partition (inf, hd::egal, sup, tl, pivot)
else
partition (inf, egal, hd::sup, tl, pivot)
in
match liste with
|[] -> []
|pivot::reste ->
let (inf, egal, sup) = partition ([], [], [],
pivot::reste, pivot) in
tri_rapide(inf) @ egal @ tri_rapide(sup)
;;
Hors ligne
#12 02-07-2011 19:34:31
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Re,
@yoshi : j'ajoute également les codes sources dans ce topic, néanmoins, je tiens à préciser que la version .pdf a un gros avantage : elle comporte également une coloration syntaxique !
Ok ! Oui, c'est bien, mais pas aussi fondamental que ça...
Les scripts Python aussi au départ : il suffit que je les charge dans l'éditeur ad hoc après copier/coller et hop ! elle revient !!!
Par contre le gros inconvénient de ton .pdf c'est qu'il ne passe pas dans un forum.
En outre, celui qui veut tester un script, inclus dans ton .pdf n'a quère que 2 options :
* Tout retaper,
* Passer par la reconnaissance de caractères...
Le pied, quoi ! :-)
Je pourrais refaire une coloration syntaxique pour tous mes scrpits Python publiés ici, mais entre balises quote et alors je perds l'indentation...
Pour caricaturer, si je te suis, il faudrait supprimer tous les scripts, et ne mettre que des liens vers des sites externes... ;-)
@+
Hors ligne
#13 02-07-2011 20:06:34
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
En outre, celui qui veut tester un script, inclus dans ton .pdf n'a quère que 2 options :
* Tout retaper,
* Passer par la reconnaissance de caractères...
Le pied, quoi ! :-)
On peut aussi faire un copier-coller des codes de mon .pdf.
Car mon .pdf est un VRAI pdf ! Pas un vague scan d'une photo d'une photocopie de brouillon mal écrit.
Pour caricaturer, si je te suis, il faudrait supprimer tous les scripts, et ne mettre que des liens vers des sites externes... ;-)
Il y a mieux : une extension pour phpBB qui fait automatiquement la coloration syntaxique : http://www.phpbb.com/community/viewtopi … 0&t=564569
Hors ligne
#14 02-07-2011 20:19:20
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
B'soir,
Mes .pdf à moi sont réalisés depuis le texte via PDFCreator libre et gratuit...
L'export intégrée avec OpenOffice est direct en couleur : ici, pas d'importance, mais souvent si, le "poids" diu document réalisé n'est pas le même...
Je m'disais aussi : pourquoi ça fonctionne sur d'autres fofos et pas le nôtre ?
Que voilà une idée qu'elle est bonne : je vais demander ça à Fred pour l'avoir le plus tôt possible...
Merci,
@+
[EDIT]
J'ai changé de liste de référence et paf ! V'la qu'il y a 3/4 tris qui déconnent graves : je vais devoir les reprendre...
J'ai vu sur le net que certains tris étaient "instables"...
C'est peut-être ce qui arrive (sauf pour le tri dichotomique)...
Je vais ajouter, après d'autres tests (chat échaudé craint l'eau froide), le tri dit radix ou par base : tous mes tests sont concluants pour l'instant...
Hélas pour la coloration syntaxique, je vois que le moteur de notre forum n'est pas phbb, mais punbb : je vais voir si ça peut marcher quand même.
Dernière modification par yoshi (03-07-2011 19:54:45)
Hors ligne
#15 05-07-2011 12:16:22
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Salut à tous,
1. Coloration syntaxique : il y a le module PunGeshi. Demande faite à Fred. Ce sera implémenté lors de la mise à jour de la version de PunBB qui est notre "moteur" de forum.
2. Les tris.
J'ai tout repris et rectifié ce qui devait l'être (ma manie des corrections "à l'oeil" de dernière minute.
Maintenant tout est ok.
J'ai ajouté le tri radix (ou tri par base)
# -*- coding: cp1252 -*-
from __future__ import division
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 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."
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."
pas=0
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."
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 tri_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..."
S=[]
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
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 à bulles",3:"Tri de Shell-Metzner",\
4:"Tri rapide (Quick Sort)",5:"Tri de fusion",6:"Tri par casiers",\
7:"Tri par tas",8:"Tri radix (ou tri par base}"}
dico={1:dicho,2:bulle,3:metzner,4:quick,5:tri_fusion,6:casiers,7:tri_par_tas,
8:tri_radix}
while 1:
aa = 1
while aa == 1:
try:
print " ***********************"
print " * Algorithmes de tris *"
print" * v. 3.4 *"
print " ***********************"
print
print
for i in xrange(1,9):
print str(i)+" - "+Menu[i]
print
print " 0 - Arrêt du programme"
print
chx = int(raw_input("Votre choix : "))
if chx > 8 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 "Liste avant tri :"
print L
print
print "Liste triée, méthode du",Menu[chx]
print
if chx == 4:
commente(chx)
S=[0]*n
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
Je vais pouvoir me remettre à la recherche d'autres méthodes via les pistes suggérées par Sebastien.
Jamais de réactions d'utilisateurs : tous sont contents (surprenant vu les correctifs nécessaires) ou personne n'est intéressé (surprenant vu les 278 visites à cette heure sur ce topic)...
@+
Hors ligne
#16 06-07-2011 11:00:45
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Re,
Ajout du tri par insertion...
Les tris 1, 2, 3 et 4 sont, sur de grandes listes, des tris lents...
# -*- coding: cp1252 -*-
from __future__ import division
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."
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."
pas=0
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."
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 tri_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..."
S=[]
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
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}"}
dico={1:dicho,2:tri_insertion,3:bulle,4:metzner,5:quick,6:tri_fusion,7:casiers,8:tri_par_tas,
9:tri_radix}
while 1:
aa = 1
while aa == 1:
try:
print " ***********************"
print " * Algorithmes de tris *"
print " * v. 3.4 *"
print " ***********************"
print
print
for i in xrange(1,10):
print str(i)+" - "+Menu[i]
print
print " 0 - Arrêt du programme"
print
chx = int(raw_input("Votre choix : "))
if chx > 9 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 "Liste avant tri :"
print L
print
print "Liste triée, méthode du",Menu[chx]
print
if chx == 4:
commente(chx)
S=[0]*n
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
Toujours pas de réactions ?
@+
Hors ligne
#19 06-07-2011 14:19:58
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Re,
Voilà pour le tri de 2000 nombres aléatoires consécutifs (1 à 2000) créés aléatoirement :
J'ai relancé 4 fois : pas de variations significatives.
Tri dichotomique : 0.141 s
Tri par Insertion : 0.296 s
Tri à bulles : 0.891 s
Tri de Shell-Metzner : 0.014 s
Tri rapide (Quick Sort) : 0.016 s
Tri de fusion : 0.016 s
Tri par casiers : 0.0 s
Tri par tas : 0.015 s
Tri radix (ou tri par base} : 0.016 s
Le grand perdant est le tri à bulles...
Une surprise (pour moi) : le tri dichotomique est bien placé. 2000 nombres, ça ne doit pas être suffisant pour qu'il soit à la traîne.
Ma machine :
AMD Phenom II X3 2,8 GHz,
2 Go RAM
XP SP3
Python 2.6.5.
Test effectué via l'IDLE Python pour Windows...
@+
[EDIT]
Avec 5000 nombres de 1 à 5000 créés aléatoirement et tous différents :
Tri dichotomique : 1.0 s
Tri par Insertion : 2.328 s
Tri à bulles : 6.687 s
Tri de Shell-Metzner : 0.031 s
Tri rapide (Quick Sort) : 0.016 s
Tri de fusion : 0.031 s
Tri par casiers : 0.0 s
Tri par tas : 0.125 s
Tri radix (ou tri par base} : 0.046 s
Pour le tri de Shell-Metzner, il semble que j'aie fait erreur : je n'avais encore pas fait de tests de vitesse...
Quand je programmais en Basic et que j'avais besoin d'un tri, c'est celui-ci que j'utilisais. Récemment, j'avais pourtant cru lire qu'il était parmi les plus lents, apparemment, j'avais tort ?
[EDIT2]
Sur 10000 entiers aléatoires de 1 à 10000 :
Tri dichotomique : 4.437 s
Tri par Insertion : 9.703 s
Tri à bulles : 27.344 s
Tri de Shell-Metzner : 0.094 s
Tri rapide (Quick Sort) : 0.046 s
Tri de fusion : 0.078 s
Tri par casiers : 0.015 s
Tri par tas : 0.109 s
Tri radix (ou tri par base} : 0.187 s
[EDIT 3]
Tous ensemble, tous ensemble, ouais !... ouais !
----------|-------------|---------
Temps
----------|-------------|---------
Tri dichotomique : 0.141 s | 1.0 s | 4.437 s
Tri par Insertion : 0.296 s | 2.328 s | 9.703 s
Tri à bulles : 0.891 s | 6.687 s | 27.344 s
Tri de Shell-Metzner : 0.014 s | 0.031 s | 0.094 s
Tri rapide : 0.016 s | 0.016 s | 0.046 s
Tri de fusion : 0.016 s | 0.031 s | 0.078 s
Tri par casiers : 0.0 s | 0.0 s | 0.015 s
Tri par tas : 0.015 s | 0.125 s | 0.109 s
Tri radix : 0.016 s | 0.046 s | 0.187 s
Dernière modification par yoshi (06-07-2011 17:52:08)
Hors ligne
#20 09-07-2011 12:24:35
- SébastienB
- Membre
- Lieu : Annecy
- Inscription : 16-06-2008
- Messages : 55
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Bonjour,
Super ces mesures. Chez moi le tri par casiers est cent fois plus performant que le tri à l'aide d'un arbre binaire de recherche pour trier une suite d'entier. Mais l'arbre binaire a l'avantage de ranger les éléments dans l'ordre en fonction de leur précédent lors du stockage de ces derniers. Donc je dirai que tout dépend du contexte pour choisir l’implémentation de telle ou telle méthode de tri.
Ci dessous mon programme pour tester le tri par arbre binaire de recherche et le tri par casiers en Java:
import java.util.Stack;
/**
* @see http://www.cs.princeton.edu/~rs/AlgsDS07/08BinarySearchTrees.pdf
*
* @param <Key>
* @param <Value>
*/
public class BST<Key extends Comparable<Key>, Value> implements Iterable<Key> {
private Node root;
private class Node {
Key key;
Value val;
Node left, right;
Node(Key key, Value val) {
this.key = key;
this.val = val;
}
}
private class BSTIterator implements Iterator<Key> {
private Stack<Node> stack = new Stack<Node>();
private void pushLeft(Node x) {
while (x != null) {
stack.push(x);
x = x.left;
}
}
BSTIterator() {
pushLeft(root);
}
public boolean hasNext() {
return !stack.isEmpty();
}
public Key next() {
Node x = stack.pop();
pushLeft(x.right);
return x.key;
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
}
private Node put(Node x, Key key, Value val) {
if (x == null)
return new Node(key, val);
int cmp = key.compareTo(x.key);
if (cmp == 0)
x.val = val;
else if (cmp < 0)
x.left = put(x.left, key, val);
else if (cmp > 0)
x.right = put(x.right, key, val);
return x;
}
@Override
public Iterator<Key> iterator() {
return new BSTIterator();
}
public Value get(Key key) {
Node x = root;
while (x != null) {
int cmp = key.compareTo(x.key);
if (cmp == 0)
return x.val;
else if (cmp < 0)
x = x.left;
else if (cmp > 0)
x = x.right;
}
return null;
}
public void put(Key key, Value val) {
root = put(root, key, val);
}
/**
* @see http://www.dailly.info/ressources/tri/java/casier.html
* @param tableau
*/
public static void triCasier(int tableau[]) {
int longueur = tableau.length;
// on parcours le tableau afin d'en récupérer les valeurs minimales et
// maximales
int mini = tableau[0];
int maxi = tableau[0];
for (int i = 1; i < longueur; i++) {
if (mini > tableau[i]) {
mini = tableau[i];
}
if (maxi < tableau[i]) {
maxi = tableau[i];
}
}
// on construit un tableau contenant le nombre d'entiers maxi-mini+1
int tmpLong = maxi - mini + 1;
int tmpTableau[] = new int[tmpLong];
// on initialise le tableau à 0
for (int i = 0; i < tmpLong; i++) {
tmpTableau[i] = 0;
}
// puis on increment le compteur correspondant à chaque entier trouvé
for (int i = 0; i < longueur; i++) {
tmpTableau[tableau[i] - mini]++;
}
// enfin, on reconstitue le tableau initial classé
int compt = 0;
for (int i = 0; i < tmpLong; i++) {
while (tmpTableau[i] > 0) {
tableau[compt] = mini + i;
tmpTableau[i]--;
compt++;
}
}
}
public static void main(String args[]) {
System.out.println("Tri par arbre binaire de recherche vs Tri par casiers");
BST<Integer, Integer> bst = new BST<Integer, Integer>();
System.out.println("Avant:");
int[] tab = new int[2936];
for (int i = 3000; i >= 65; i--) {
System.out.print((char) i);
bst.put(i, i);
tab[i-65]=i;
System.out.print("("+tab[i-65]+") ");
}
System.out.println();
Integer k = new Integer(65);
long start = System.nanoTime();
while ((k = bst.get(k)) != null)
k++;
double tps = (System.nanoTime() - start) * 0.000000001;
System.out
.println("Le temps d'execution pour le tri a l'aide d'un arbre binaire de recherche est: "
+ tps + " sec.");
start = System.nanoTime();
triCasier(tab);
tps = (System.nanoTime() - start) * 0.000000001;
System.out
.println("Le temps d'execution pour le tri par casier est: "
+ tps + " sec.");
k = 65; // Réinitialiser le noeud de départ
System.out.println("Après:");
while ((k = bst.get(k)) != null) {
System.out.print((char) k.intValue());
System.out.print("("+tab[k-65]+") ");
k++;
}
}
}
Avant:
?(3000) ?(2999) [...] Z(90) Y(89) X(88) W(87) V(86) U(85) T(84) S(83) R(82) Q(81) P(80) O(79) N(78) M(77) L(76) K(75) J(74) I(73) H(72) G(71) F(70) E(69) D(68) C(67) B(66) A(65)
Le temps d'execution pour le tri a l'aide d'un arbre binaire de recherche est: 0.059544678000000004 sec.
Le temps d'execution pour le tri par casier est: 5.86445E-4 sec.
Après:
A(65) B(66) C(67) D(68) E(69) F(70) G(71) H(72) I(73) J(74) K(75) L(76) M(77) N(78) O(79) P(80) Q(81) R(82) S(83) T(84) U(85) V(86) W(87) X(88) Y(89) Z(90) [...] ?(2999) ?(3000)
@+
Hors ligne
#21 09-07-2011 13:43:04
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Re,
Le problème du tri par casiers est que si parmi mes 10000 nombres entiers consécutifs, j'en retire un au hasard et qu'à la place j'inscris 40 000 par ex, il va devoir créer puis balayer 40 000 casiers et c'est là que le handicap va intervenir...
Alors que ça ne changera rien pour aucune des autres méthodes de tri.
Au passage, Python n'est pas réputé pour sa rapidité, au contraire du C par exemple
Merci de ta contribution.
Caractéristiques techniques de ta machine ?
Au passage, peux-tu me dire si le programme en java répondant à ce pseudo-code ci :
http://lwh.free.fr/pages/algo/tri/tri_batcher.htm
(clic en bas de page) est fonctionnel ?
Je l'ai traduit bêtement en Python et il n'effectue aucun tri.
Je l'ai modifié et il fonctionne... imparfaitement : tri incomplet !
Donc je rate quelque chose quelque part.
Au passage, j'ai vérifié des sources en anglais : Batcher a l'air d'avoir découvert 2 tris qui ne ressemblent pas à ça.
J'ai plutôt l'impression que c'est le tri de Bose-Nelson présenté ici :
http://pages.ripco.net/~jgamble/nw.html
@+
Hors ligne
#22 09-07-2011 16:22:51
- SébastienB
- Membre
- Lieu : Annecy
- Inscription : 16-06-2008
- Messages : 55
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Oui c'est fonctionnel. Ce tri semble performant.
public class BatcherVsBoseNelson{
static int nb_comparaisons = 0;
static int nb_echanges = 0;
static void sort(int a[]) {
int p, q, r, d, n, p2;
boolean fin;
n = a.length;
p = 1;
while (p <= n)
p = p << 1;
p2 = p >>> 1;
while (p >= 2) {
p = p >>> 1;
q = p2;
r = 0;
d = p;
fin = false;
while (!fin) {
for (int i = 0; i < n - d; i++) {
if ((i & p) == r) {
if (a[i] > a[i + d]) {
// Echange de i et i+d
int temp = a[i];
a[i] = a[i + d];
a[i + d] = temp;
nb_echanges++;
}
nb_comparaisons++;
}
}
if (q != p) {
d = q - p;
q = q >>> 1;
r = p;
fin = false;
} else
fin = true;
}
}
} // Fin du tri
public static void main(String args[]) {
int[] tab = new int[3000];
Random r = new Random();
for (int i = 0; i < 3000; i++) {
tab[i] = r.nextInt(3000);
}
long start = System.nanoTime();
sort(tab);
double tps = (System.nanoTime() - start) * 0.000000001;
System.out.println("Le temps d'execution pour le tri Batcher est: "
+ tps + " sec. "+nb_echanges+" echanges et "+nb_comparaisons+" comparaisons.");
for (int i = 0; i < 3000; i++) {
System.out.println(tab[i]);
}
}
}
1
1
2
3
6
8
11
12
14
18
20
21
22
23
27
28
29
33
33
33
34
36
38
41
43
43
44
45
46
47
47
47
47
49
50
50
51
51
52
54
55
55
56
56
57
57
57
58
60
61
61
63
63
64
64
65
66
67
67
68
68
70
72
73
73
73
74
74
74
75
76
77
77
78
78
81
82
82
83
83
84
84
84
86
87
87
88
89
89
91
93
93
94
94
94
96
96
98
98
98
99
100
100
102
103
103
105
106
107
107
107
108
109
109
110
111
112
115
118
120
120
123
123
125
125
127
128
128
129
129
130
130
130
131
131
132
132
133
134
135
135
137
139
140
141
142
142
144
147
149
150
152
155
160
164
166
170
170
171
172
175
176
178
180
180
180
180
180
182
182
183
184
184
184
184
187
188
189
191
192
192
193
193
194
194
194
196
198
200
200
201
206
206
207
208
208
208
209
210
211
211
212
214
215
220
221
222
223
223
226
226
230
230
231
232
233
233
234
234
235
236
238
239
239
240
240
241
242
243
243
243
244
245
247
248
249
251
251
252
252
253
254
255
255
259
259
260
261
262
263
263
265
266
269
269
269
269
270
271
272
273
273
273
277
277
278
278
279
279
280
280
282
282
283
283
285
287
288
288
290
290
290
292
292
292
294
294
295
296
296
297
297
297
298
300
300
301
305
305
307
307
309
310
310
311
311
312
314
315
315
315
318
319
319
319
321
321
323
323
326
329
329
330
331
331
331
336
337
338
338
339
339
341
341
342
343
343
345
346
346
347
347
348
351
353
356
357
359
359
360
360
361
362
362
363
363
364
364
365
368
369
370
370
370
371
372
375
375
376
378
381
382
383
386
387
387
388
389
389
390
391
391
392
392
392
395
396
396
396
399
399
400
401
402
402
404
405
405
405
406
406
408
408
408
411
415
415
416
416
417
418
419
420
423
423
423
424
424
425
426
427
428
428
428
429
429
431
435
437
443
445
445
445
449
449
450
450
452
455
455
455
455
456
457
459
460
464
465
465
466
466
467
467
467
467
467
469
469
470
473
478
481
481
482
482
486
487
489
491
492
496
498
500
501
502
502
503
504
505
507
507
512
512
513
515
517
517
518
520
520
522
523
525
525
527
527
528
529
529
529
530
531
531
532
533
534
534
535
535
535
536
538
538
539
542
542
544
544
546
547
548
548
549
549
552
554
556
559
561
564
566
568
569
570
572
572
575
575
578
579
579
580
581
582
583
583
587
587
588
590
593
594
594
595
599
599
600
601
604
604
606
607
609
610
610
611
613
614
614
614
617
620
621
621
622
622
624
625
626
627
629
631
632
634
636
638
639
639
640
641
641
642
643
643
644
646
648
649
653
653
654
654
658
659
660
660
662
665
665
667
667
670
670
671
671
673
674
674
674
675
675
676
676
676
678
678
681
683
684
688
689
690
691
692
693
697
697
697
697
699
699
700
701
701
702
703
703
703
703
704
704
704
704
705
706
706
707
708
708
708
708
709
712
714
715
716
717
717
718
720
722
726
726
727
728
729
729
730
731
732
732
732
734
735
735
736
736
737
737
742
744
744
745
746
746
746
747
750
752
752
753
756
756
757
758
758
759
759
760
760
760
762
762
762
762
764
764
764
767
769
770
770
771
775
775
776
778
779
779
780
782
783
783
784
784
785
785
785
786
788
788
789
792
793
793
795
796
797
797
798
798
799
800
800
800
801
802
804
804
805
805
806
808
808
808
809
812
812
813
814
815
816
819
819
819
821
821
821
822
823
825
826
828
828
828
829
829
832
832
833
833
835
836
837
839
839
841
842
843
843
843
845
846
846
847
849
852
852
854
855
856
856
857
857
859
859
859
860
860
860
861
862
864
866
866
868
871
872
875
876
877
881
884
884
886
889
889
889
890
892
892
893
893
895
896
897
897
899
900
900
902
903
904
905
906
906
909
911
911
911
911
912
912
913
913
914
914
916
917
919
921
924
924
924
925
926
927
928
928
929
929
930
930
932
936
936
937
938
939
941
942
947
947
948
949
952
953
953
957
957
958
959
959
960
962
965
965
965
966
969
970
971
972
972
972
973
975
976
977
977
979
980
981
983
984
984
985
987
988
989
990
993
994
996
997
999
999
1001
1003
1003
1005
1007
1007
1009
1010
1011
1014
1014
1014
1014
1016
1016
1017
1017
1017
1018
1018
1019
1020
1020
1023
1023
1024
1025
1025
1027
1027
1027
1029
1031
1031
1031
1031
1032
1033
1034
1035
1037
1039
1040
1040
1042
1043
1044
1046
1047
1052
1055
1057
1059
1059
1059
1059
1061
1062
1063
1065
1065
1065
1066
1068
1069
1071
1071
1073
1073
1076
1077
1080
1081
1082
1084
1085
1088
1088
1089
1090
1091
1091
1092
1093
1094
1095
1096
1098
1099
1099
1099
1099
1100
1101
1101
1102
1102
1104
1105
1106
1106
1106
1107
1109
1109
1110
1110
1111
1111
1112
1112
1115
1117
1118
1119
1120
1120
1121
1121
1121
1121
1121
1123
1124
1125
1125
1125
1127
1128
1128
1129
1129
1131
1132
1133
1133
1135
1135
1138
1138
1139
1141
1142
1143
1143
1144
1144
1144
1145
1146
1147
1147
1152
1153
1156
1157
1158
1158
1161
1162
1163
1164
1164
1165
1166
1167
1168
1168
1168
1169
1169
1169
1169
1170
1172
1172
1172
1172
1173
1173
1175
1175
1175
1176
1177
1177
1177
1178
1180
1181
1181
1181
1182
1182
1183
1183
1184
1184
1185
1186
1188
1189
1189
1190
1190
1196
1197
1197
1197
1200
1201
1201
1203
1203
1203
1204
1209
1210
1210
1211
1211
1211
1212
1212
1217
1217
1217
1219
1221
1222
1223
1223
1223
1224
1225
1225
1226
1226
1226
1226
1228
1229
1231
1232
1233
1234
1235
1236
1239
1239
1240
1241
1243
1245
1245
1245
1246
1247
1247
1247
1248
1248
1250
1254
1254
1255
1255
1255
1256
1258
1259
1259
1260
1262
1262
1262
1262
1263
1265
1265
1266
1267
1267
1269
1271
1271
1271
1271
1272
1272
1273
1273
1273
1274
1277
1277
1277
1279
1281
1281
1282
1283
1284
1284
1285
1285
1286
1288
1288
1288
1288
1288
1288
1289
1291
1292
1294
1294
1295
1296
1298
1298
1298
1298
1299
1302
1304
1305
1306
1306
1308
1309
1309
1310
1310
1311
1316
1316
1316
1318
1318
1318
1319
1321
1322
1324
1325
1327
1328
1329
1331
1331
1333
1333
1333
1334
1335
1337
1337
1338
1338
1338
1339
1341
1344
1345
1346
1346
1348
1348
1348
1349
1349
1350
1351
1352
1352
1352
1354
1355
1355
1355
1356
1359
1360
1361
1361
1362
1362
1362
1362
1362
1363
1363
1363
1363
1365
1365
1365
1366
1366
1368
1369
1369
1371
1371
1371
1373
1374
1375
1375
1376
1376
1377
1377
1378
1379
1379
1379
1379
1380
1382
1382
1383
1384
1385
1385
1386
1387
1387
1387
1387
1388
1388
1388
1389
1389
1389
1389
1390
1392
1392
1392
1392
1393
1394
1394
1397
1398
1399
1399
1399
1399
1400
1401
1402
1402
1402
1404
1405
1405
1406
1406
1407
1407
1407
1407
1408
1409
1413
1413
1413
1414
1415
1418
1419
1419
1420
1420
1421
1421
1422
1422
1422
1423
1424
1425
1426
1426
1428
1428
1430
1432
1435
1437
1438
1438
1438
1440
1440
1442
1442
1443
1444
1445
1445
1449
1452
1454
1454
1456
1457
1458
1460
1462
1462
1463
1464
1466
1468
1472
1472
1473
1473
1475
1479
1481
1481
1481
1482
1483
1484
1488
1490
1491
1492
1492
1493
1496
1499
1501
1503
1503
1505
1505
1506
1506
1508
1508
1509
1510
1511
1512
1512
1515
1515
1518
1520
1520
1521
1522
1524
1524
1525
1525
1528
1528
1528
1529
1530
1530
1532
1532
1533
1536
1537
1539
1539
1542
1543
1544
1544
1545
1547
1549
1549
1550
1552
1553
1553
1554
1555
1556
1557
1557
1557
1558
1559
1561
1562
1562
1562
1562
1562
1563
1563
1563
1569
1569
1570
1571
1573
1573
1574
1575
1579
1579
1580
1580
1581
1581
1582
1582
1583
1583
1584
1584
1584
1584
1585
1585
1585
1586
1586
1586
1587
1588
1588
1589
1589
1590
1592
1592
1596
1599
1600
1601
1601
1601
1602
1603
1605
1606
1607
1607
1607
1607
1608
1608
1608
1608
1608
1609
1610
1610
1610
1611
1613
1613
1613
1614
1614
1614
1614
1615
1617
1621
1623
1627
1628
1628
1628
1628
1629
1630
1631
1631
1632
1632
1633
1635
1636
1637
1637
1637
1638
1638
1640
1640
1641
1641
1642
1642
1645
1645
1646
1648
1651
1652
1652
1656
1657
1659
1659
1659
1659
1660
1660
1662
1667
1668
1669
1669
1670
1670
1670
1670
1671
1672
1672
1675
1676
1676
1676
1678
1679
1679
1679
1681
1682
1686
1686
1688
1689
1690
1690
1692
1692
1692
1693
1694
1695
1695
1697
1699
1699
1700
1702
1703
1704
1704
1705
1706
1706
1708
1708
1708
1708
1709
1710
1710
1711
1712
1712
1712
1713
1714
1714
1715
1715
1716
1717
1719
1720
1720
1721
1721
1722
1725
1727
1728
1729
1730
1730
1733
1734
1738
1740
1743
1743
1747
1748
1752
1752
1752
1753
1753
1754
1755
1755
1757
1757
1757
1759
1760
1760
1761
1762
1763
1763
1768
1769
1769
1771
1771
1771
1772
1772
1773
1773
1774
1775
1776
1776
1778
1778
1778
1779
1779
1779
1780
1781
1782
1783
1783
1786
1787
1787
1789
1790
1791
1791
1795
1795
1796
1797
1798
1800
1800
1801
1802
1803
1803
1805
1805
1807
1808
1808
1809
1810
1811
1812
1812
1812
1812
1812
1812
1814
1815
1815
1816
1819
1821
1821
1822
1823
1824
1824
1825
1826
1826
1828
1828
1834
1834
1836
1837
1837
1838
1839
1841
1843
1843
1843
1844
1844
1846
1847
1847
1848
1849
1851
1851
1851
1852
1853
1854
1856
1857
1859
1859
1865
1866
1868
1868
1869
1869
1870
1870
1873
1877
1880
1880
1880
1881
1882
1882
1886
1887
1887
1887
1888
1889
1890
1891
1891
1892
1894
1894
1895
1895
1896
1896
1900
1901
1907
1911
1912
1913
1913
1914
1915
1915
1915
1917
1917
1918
1918
1919
1921
1922
1923
1926
1926
1927
1927
1929
1929
1930
1931
1933
1933
1941
1943
1945
1946
1946
1946
1947
1948
1949
1949
1950
1950
1952
1954
1955
1955
1956
1958
1958
1958
1958
1958
1960
1960
1960
1961
1961
1963
1964
1966
1966
1967
1967
1967
1968
1970
1971
1972
1972
1972
1973
1974
1975
1976
1978
1978
1979
1980
1982
1983
1983
1984
1984
1985
1985
1985
1985
1986
1988
1989
1989
1991
1991
1992
1993
1994
1995
1995
1995
1996
1998
2000
2001
2001
2001
2002
2002
2003
2004
2005
2006
2006
2010
2010
2010
2012
2014
2018
2018
2021
2021
2022
2022
2022
2023
2027
2027
2030
2031
2031
2032
2034
2035
2037
2037
2037
2038
2041
2042
2042
2045
2045
2046
2046
2047
2049
2050
2051
2051
2054
2056
2057
2057
2059
2059
2060
2060
2060
2060
2061
2061
2061
2061
2063
2063
2064
2064
2065
2066
2066
2068
2068
2068
2069
2069
2069
2071
2071
2073
2073
2075
2076
2077
2077
2078
2078
2079
2079
2080
2081
2081
2084
2084
2084
2086
2086
2088
2089
2089
2089
2089
2089
2093
2094
2094
2096
2097
2097
2099
2100
2100
2102
2103
2103
2103
2103
2103
2106
2107
2109
2109
2110
2110
2111
2113
2113
2113
2113
2115
2118
2118
2121
2121
2121
2122
2122
2122
2122
2123
2123
2124
2124
2125
2130
2131
2132
2134
2135
2137
2137
2138
2140
2141
2142
2145
2145
2146
2146
2147
2147
2149
2151
2151
2152
2154
2155
2156
2158
2158
2158
2161
2162
2165
2166
2167
2167
2168
2170
2170
2170
2171
2172
2175
2177
2177
2178
2179
2180
2182
2182
2183
2183
2183
2184
2184
2187
2188
2189
2193
2194
2195
2196
2197
2199
2203
2203
2203
2205
2205
2206
2206
2207
2208
2209
2212
2212
2214
2217
2217
2217
2218
2219
2219
2219
2220
2221
2221
2222
2222
2222
2223
2224
2225
2226
2226
2227
2227
2227
2228
2228
2228
2230
2232
2232
2232
2233
2234
2235
2235
2241
2243
2244
2244
2245
2245
2246
2247
2249
2249
2249
2250
2250
2250
2254
2255
2256
2258
2259
2260
2260
2261
2262
2262
2262
2264
2264
2266
2266
2267
2267
2268
2269
2271
2272
2273
2274
2274
2274
2275
2277
2277
2278
2278
2279
2281
2281
2281
2282
2283
2286
2288
2289
2290
2294
2296
2297
2299
2299
2300
2301
2302
2303
2304
2306
2306
2307
2308
2309
2311
2311
2312
2313
2313
2314
2315
2315
2316
2316
2316
2317
2317
2320
2321
2323
2323
2323
2326
2326
2327
2329
2331
2331
2332
2333
2334
2335
2336
2338
2338
2342
2342
2342
2347
2347
2348
2352
2352
2354
2355
2357
2357
2359
2361
2363
2363
2364
2364
2365
2365
2366
2366
2368
2369
2370
2370
2370
2371
2373
2374
2374
2374
2376
2377
2377
2377
2378
2378
2379
2380
2381
2382
2383
2384
2385
2386
2386
2387
2388
2388
2388
2391
2392
2392
2392
2393
2395
2396
2396
2396
2396
2398
2399
2399
2399
2400
2402
2403
2403
2404
2406
2408
2410
2410
2412
2413
2414
2415
2416
2416
2419
2421
2422
2423
2423
2423
2423
2427
2428
2429
2432
2434
2435
2435
2436
2439
2440
2440
2441
2441
2443
2443
2443
2447
2447
2448
2450
2450
2453
2454
2455
2455
2457
2458
2458
2458
2459
2460
2460
2460
2461
2461
2463
2464
2468
2468
2469
2469
2470
2471
2471
2473
2473
2474
2476
2476
2476
2477
2478
2479
2479
2480
2482
2483
2484
2485
2485
2489
2492
2496
2497
2497
2498
2499
2500
2500
2501
2503
2504
2505
2505
2505
2505
2507
2508
2509
2510
2511
2511
2512
2512
2513
2513
2515
2515
2516
2516
2517
2517
2519
2521
2522
2522
2524
2524
2525
2526
2526
2528
2528
2528
2529
2532
2533
2533
2533
2533
2534
2536
2536
2536
2537
2537
2538
2539
2539
2539
2540
2540
2540
2542
2542
2544
2545
2546
2546
2546
2546
2548
2550
2550
2552
2554
2555
2555
2555
2557
2559
2559
2561
2561
2562
2563
2564
2564
2565
2568
2568
2568
2569
2571
2574
2576
2578
2579
2580
2581
2581
2581
2582
2582
2583
2585
2586
2588
2589
2589
2591
2592
2592
2594
2595
2596
2598
2600
2600
2602
2602
2604
2606
2607
2608
2609
2613
2614
2618
2619
2619
2621
2623
2626
2627
2628
2628
2629
2629
2629
2630
2631
2632
2633
2633
2634
2635
2635
2635
2635
2636
2638
2638
2639
2643
2645
2645
2647
2647
2647
2647
2648
2649
2650
2650
2651
2651
2652
2653
2653
2656
2657
2658
2658
2660
2660
2663
2665
2666
2667
2671
2674
2675
2675
2676
2676
2677
2677
2677
2677
2678
2678
2678
2679
2679
2679
2679
2680
2682
2682
2683
2684
2684
2685
2685
2686
2687
2688
2690
2693
2694
2695
2697
2698
2698
2698
2699
2699
2701
2702
2703
2704
2705
2709
2709
2712
2713
2714
2715
2715
2715
2716
2716
2716
2717
2717
2717
2718
2718
2719
2719
2720
2722
2723
2724
2725
2725
2726
2726
2728
2729
2731
2732
2733
2734
2736
2737
2739
2739
2741
2741
2744
2744
2745
2745
2746
2748
2749
2750
2751
2753
2754
2754
2754
2754
2756
2757
2757
2757
2757
2758
2758
2758
2760
2762
2764
2767
2767
2768
2769
2769
2772
2772
2773
2774
2776
2777
2777
2778
2779
2780
2781
2783
2783
2785
2785
2786
2786
2787
2787
2791
2792
2792
2793
2794
2794
2795
2795
2797
2797
2798
2799
2799
2800
2801
2803
2804
2805
2806
2807
2807
2811
2813
2814
2814
2815
2815
2815
2818
2820
2822
2824
2824
2825
2826
2828
2830
2831
2832
2832
2834
2837
2837
2838
2839
2843
2843
2843
2844
2846
2847
2848
2853
2853
2855
2856
2856
2857
2857
2859
2861
2863
2863
2865
2866
2867
2868
2869
2870
2870
2872
2872
2872
2872
2873
2873
2873
2875
2876
2877
2878
2879
2880
2881
2882
2882
2885
2887
2887
2887
2888
2890
2892
2893
2894
2894
2895
2897
2898
2898
2899
2899
2899
2900
2902
2903
2903
2903
2904
2904
2905
2905
2906
2906
2906
2906
2907
2908
2908
2909
2913
2913
2913
2913
2919
2919
2920
2921
2923
2924
2925
2926
2928
2930
2930
2930
2931
2933
2933
2936
2937
2937
2938
2939
2939
2940
2941
2942
2943
2944
2945
2947
2947
2948
2948
2948
2949
2950
2951
2952
2953
2954
2954
2954
2958
2958
2958
2959
2959
2960
2962
2962
2963
2964
2965
2965
2966
2966
2967
2967
2968
2968
2970
2971
2972
2973
2974
2978
2979
2979
2981
2981
2982
2984
2985
2985
2989
2990
2991
2993
2994
2995
2995
2996
2999
tri de Batcher en Python:
http://en.wikipedia.org/wiki/Batcher_odd-even_mergesort
Pour le Java, voilà un autre site connu mais dont le lien ici a le mérite de pointer sur un complément d'informations utiles et exactes:
http://www.commentcamarche.net/contents … avaop.php3
@+
Dernière modification par SébastienB (10-07-2011 17:42:30)
Hors ligne
#23 09-07-2011 20:22:20
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Salut,
Merci pour le lien, je l'avais déjà : mais la méthode proposée est différente de celle que tu as implémentée, toi...
Si la méthode marche en Java, sa transcription en Python doit marcher aussi : aucune justification du contraire.
Or, je viens de suivre pas à pas ce que tu as fait, sauf pour la détermination de p où je suis passé par les ln puis l'arrondi à l'entier supérieur...
Questions à tout hasard :
p = p << 1; c'est la multiplication par 2 ?
p2 = p >>> 1; c'est une division par 2 ?
Si oui, alors mon code transcrit est conforme au tien.
Et chez moi sur une liste de 13 nombres à la fin, un d'entre eux est mal rangé...
Bizarre !
@+
[EDIT]
Bon, j'ai trouvé, mais du diable si je sais pourquoi...
J'ai fait plusieurs essais, en rajoutant d'autres nombres à la fin de ma liste et, ô surprise, c'était toujours le même qui était mal rangé !!!
Invraisemblable...
Je l'ai effacé de ma liste, l'ai remis à la même place et retenté l'expérience : maintenant ça colle !
En tout état de cause, le pseudo-code du site que j'avais mis en lien est incorrect : tant la version JAVA que la version Pascal contiennent des éléments supplémentaires...
Et je maintiens que ce n'est pas le tri de Batcher (d'abord, il y en a deux) mais celui de Bose-Nelson
Hors ligne
#24 10-07-2011 10:25:51
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 385
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Bonjour,
Ajout d'un tri, pour moi incorrectement qualifié de tri de Batcher, je penche plutôt pour le tri de Bose-Nelson (avis des spécialistes ? Je suis preneur...)
Les temps globaux donnés ont calculés sur une la moyenne des temps obtenus après 5 choix de 2000, 5000, 10000 nombres choisis "aléatoirement" par le programme...
Code modifié en conséquence :
# -*- 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 Bose(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)/log(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
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 Bose-Nelson"}
dico={1:dicho,2:tri_insertion,3:bulle,4:metzner,5:quick,6:tri_fusion,7:casiers,8:tri_par_tas,
9:radix,10:Bose}
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,11):
print "%2i" % i,"-",Menu[i]
print
print " 0 - Arrêt du programme"
print
chx = int(raw_input("Votre choix : "))
if chx > 10 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 "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
Moyenne des temps :
----------|-------------|---------
Temps
----------|-------------|---------
Tri dichotomique : 0.146 s | 0.959 s | 4.397 s
Tri par Insertion : 0.3 s | 2.075 s | 9.065 s
Tri à bulles : 0.859 s | 5.872 s | 26.256 s
Tri de Shell-Metzner : 0.013 s | 0.041 s | 0.084 s
Tri rapide : 0.012 s | 0.022 s | 0.037 s
Tri de fusion : 0.016 s | 0.031 s | 0.097 s
Tri par casiers : 0.006 s | 0.006 s | 0.015 s
Tri par tas : 0.016 s | 0.049 s | 0.094 s
Tri radix : 0.022 s | 0.053 s | 0.156 s
Tri de Bose-Nelson : 0.028 s | 0.091 s | 0.256 s
@+
Hors ligne
#25 10-07-2011 18:02:52
- SébastienB
- Membre
- Lieu : Annecy
- Inscription : 16-06-2008
- Messages : 55
Re : [Python, C, Java, Pascal, LISP, OCAML....] Algorithmes de tri
Re,
UP, j'ai répondu dans mon avant dernier message au dessus.
Vu que je ne suis ni Batcher, ni Bose ou Nelson mais un illustre inconnu, je ne pouvais pas le savoir!
Mais merci pour l'ajout.
@+
Hors ligne