Je suis dans la rédaction d'un article pour la prochaine gazette (pas le futur HS
), et il propose l'implémentation de différents algo pour réaliser des tris (de l'immonde tri à bulle au tri Shell, en passant par le tri insertion et le tri sélection).Je me limite à ces 4 tris qui sont des tris sur place adaptés aux limites techniques de nos machines.
Cependant, j'aimerais quelques avis sur leur optimisation (en respectant les algos) et surtout, avoir des benchs sur différentes machines (j'en fait, mais je n'ai pas tout...) que vous pourriez aussi réaliser si vous en avez l'envie.
Tout d'abord le tri à bulle (beurk, mais on n'y a droit dans n'importe quel tuto internet sur le tri, mais ça donne un point de repère).
Code : Tout sélectionner
10 CLS:CLEAR:RANDOMIZE TIMER
20 DIM B(2000)
30 M1=0:V1=0:L=0:MA1=0:MI1=0
40 INPUT"nb de val=";V
50 INPUT"nb de cycles=";L0
60 L=L+1:T0=TIMER:FOR I=0 TO V-1:B(I)=INT(RND*10000):NEXT I:T1=TIMER
70 P=0:FOR I=0 TO V-2
80 IF B(I)<B(I+1) THEN T=B(I):B(I)=B(I+1):B(I+1)=T:P=1
90 NEXT I
100 IF P=1 THEN 70
110 T2=TIMER:H1=T2-T1
120 IF H1>MA1 THEN MA1=H1
130 IF H1<MI1 OR MI1=0 THEN MI1=H1
140 M1=M1+H1:V1=V1+H1*H1
150 PRINT L;" tps tri = ";:PRINT USING"#.##";H1
160 IF L<L0 THEN 60
170 PRINT"min : ";:PRINT USING"#.##";MI1;:PRINT" max : ";:PRINT USING"#.##";MA1
180 PRINT"Tps : ";:PRINT USING"#.##";M1/L0;:PRINT" EcTyp : ";:PRINT USING"#.##";SQR(V1/L0-(M1/L0)^2)Ce sont les lignes 70 à 100 qui réalisent vraiment ce tri, avec la ligne 40 et une partie de la 60 pour la création du tableau à trier.
Ce qui serait intéressant : avoir des temps moyens pour 10, 20, 30, 50, 70, 100 éléments. Sans pour autant dépasser 1 minute pour un tri (pas la peine non plus de perdre trop de temps)
Un exemple sur PC1600 :
- 10 éléments : 2 secondes et écart type de 0,63
- 20 élements : 9,2 secondes et ec de 0,98
- 30 éléments : 21 secondes et ec de 2,05
- 50 éléments : 58,7 secondes et ec de 4,54
On remarque d'ailleurs que le ratio (nb éléments)^2/temps est quasi constant.
Je vais ajouter les autres algos dans d'autres messages dans ce fil.
N'hésitez pas à proposer des codes pour d'autres systèmes (en LMS par exemple, je l'ai fait sur ma HP15C et 35S, je vous les proposerai aussi).
Bon amusement (ou pas
)
