tri de listes
Modérateur : Politburo
tri de listes
Bonjour à tous
En Ti basic que ce soit sur les ti 82,83 ,89,92 ou nspire les instructions sortA et sortD
permettant de trier une liste accepte plusieurs listes en arguments, les éléments des autres
listes suivent le mouvement de la première liste triée et ainsi la cohérence des données est conservée.
Hors il semble que sur les calculatrices Hp 39gii,50 et prime cela soit impossible, car la fonction Sort n'accepte
qu'une seule liste en argument, j'ai essayé de contourner le problème avec une liste de listes, sur 39 et 50
j'obtiens une erreur, sur prime cela passe mais je n'obtiens pas le résultat escompté, elle semble trié les listes
les unes par rapport aux autres et pas les élèments.
Cela me semble curieux, est-ce que quelque chose m'échappe ?
En Ti basic que ce soit sur les ti 82,83 ,89,92 ou nspire les instructions sortA et sortD
permettant de trier une liste accepte plusieurs listes en arguments, les éléments des autres
listes suivent le mouvement de la première liste triée et ainsi la cohérence des données est conservée.
Hors il semble que sur les calculatrices Hp 39gii,50 et prime cela soit impossible, car la fonction Sort n'accepte
qu'une seule liste en argument, j'ai essayé de contourner le problème avec une liste de listes, sur 39 et 50
j'obtiens une erreur, sur prime cela passe mais je n'obtiens pas le résultat escompté, elle semble trié les listes
les unes par rapport aux autres et pas les élèments.
Cela me semble curieux, est-ce que quelque chose m'échappe ?
Ti(s) 60, 62 Galaxy, 66, 67 Galaxy, 68, 74 Basical 80, 81, 82, 83+, 83 CE, 84+SE, 85, 86, 89, 89 titanium, 92, 95 Procalc, v200, nSpire cx
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Re: tri de listes
Bonjour à tous
Bon après le diagnostic, le remède.
En Ti basic SortA est une instruction qui modifie directement les variables transmises.
Elle renvoie une erreur si les listes ne sont pas toutes de la même longueur.
Pour la Prime et la hp 50g voici SORTM, qui est une fonction, elle accepte des listes de longueurs différentes,
bien sur si la première, celle qui sert de référence,est plus longue que les suivantes elle renvoie une erreur,
par contre si les suivantes sont plus longues seules les données correspondantes avec la première liste seront
triées, les autres seront conservées dans l'ordre de départ.
exemple: SORTM({{"b","c","a"},{10,20,30,40,50}}) renverra ->{ {"a","b","c"},{30,10,20,40,50}}
On peut aussi, utiliser SORTM avec une seule liste, elle renverra alors 2 listes:
la liste transmise triée et une liste d'index correspondant au mouvements effectués.
exemple: SORTM({"b","c","a"}) renverra -> {{"a","b","c"},{3,1,2}}
En Ti basic on peut trier par ordre croissant sortA ou décroissant sortD, ici on peut utiliser REVLIST après le tri pour l'ordre
décroissant.
Pour le tri j'ai utilisé l'algo du tri à bulles, j'ai pompé ça dans l'OP n°23
Voici le code pour la Prime:
et pour la 50g
Le code pour la 50g est sûrement perfectible, arrêt plus propre en cas d'erreur, on pourrait aussi
sauvegarder les flags puisque l'on utilise le n° 128.
Voilà si vous avez des remarques n'hésitez pas.
EDIT: correction sur l'exemple pour utiliser la fonction avec plusieurs listes, on transmet une liste de listes {{liste 1}{liste 2}{liste n}}
Bon après le diagnostic, le remède.
En Ti basic SortA est une instruction qui modifie directement les variables transmises.
Elle renvoie une erreur si les listes ne sont pas toutes de la même longueur.
Pour la Prime et la hp 50g voici SORTM, qui est une fonction, elle accepte des listes de longueurs différentes,
bien sur si la première, celle qui sert de référence,est plus longue que les suivantes elle renvoie une erreur,
par contre si les suivantes sont plus longues seules les données correspondantes avec la première liste seront
triées, les autres seront conservées dans l'ordre de départ.
exemple: SORTM({{"b","c","a"},{10,20,30,40,50}}) renverra ->{ {"a","b","c"},{30,10,20,40,50}}
On peut aussi, utiliser SORTM avec une seule liste, elle renverra alors 2 listes:
la liste transmise triée et une liste d'index correspondant au mouvements effectués.
exemple: SORTM({"b","c","a"}) renverra -> {{"a","b","c"},{3,1,2}}
En Ti basic on peut trier par ordre croissant sortA ou décroissant sortD, ici on peut utiliser REVLIST après le tri pour l'ordre
décroissant.
Pour le tri j'ai utilisé l'algo du tri à bulles, j'ai pompé ça dans l'OP n°23
Voici le code pour la Prime:
Code : Tout sélectionner
EXPORT SORTM(o)
BEGIN
LOCAL f,i,j,d,n;
LOCAL e,k,l,z;
IF TYPE(o[1])==6 THEN
l:=o[1];f:=1;
ELSE
l:=o;
END;
d:=SIZE(l);
k:=MAKELIST(I,I,1,d);
FOR i FROM 1 TO d-1 DO
FOR j FROM i+1 TO d DO
IF l[j]<l[i] THEN
e:={l[i],k[i]};
l[i]:=l[j];k[i]:=k[j];
l[j]:=e[1];k[j]:=e[2];
END;
END;
END;
IF f THEN
o[1]:=l;n:=SIZE(o);
FOR i FROM 2 TO n DO
z:=SIZE(o[i]);l:={};
FOR j FROM 1 TO d DO
l[j]:=o(i,k[j]);
END;
o[i]:=IFTE(z>d,CONCAT(l,SUB(o[i],j,z)),l);
END;
o;
ELSE
{l,k};
END;
END;
Code : Tout sélectionner
<< 128. CF DUP 1. GET DUP TYPE
IF 5. ==
THEN 128. SF
ELSE DROP
END DUP SIZE
<< n
>> 'n' 1. 4. PICK 1. SEQ -> l d k
<< 1. d 1. -
FOR i i 1. + d
FOR j 'l' i GET 'l' j GET DUP2
IF >
THEN 'l' i ROT PUT 'l' j ROT PUT 'k' i GET 'k' j GET 'k' i ROT PUT 'k' j ROT PUT
ELSE DROP2
END
NEXT
NEXT
IF 128. FC?
THEN l k 2. ->LIST
ELSE 1. l PUT DUP SIZE 2. SWAP
FOR i { } SWAP DUP i GET 1. d
FOR j DUP k j GET GET 4. ROLL + UNROT
NEXT DUP SIZE d DUP2
IF >
THEN 1. + SWAP SUB REVLIST ROT + SWAP
ELSE 3. DROPN
END i ROT REVLIST PUT
NEXT
END
>>
>>
sauvegarder les flags puisque l'on utilise le n° 128.
Voilà si vous avez des remarques n'hésitez pas.
EDIT: correction sur l'exemple pour utiliser la fonction avec plusieurs listes, on transmet une liste de listes {{liste 1}{liste 2}{liste n}}
Modifié en dernier par tyann le 19 janv. 2014 12:24, modifié 2 fois.
Ti(s) 60, 62 Galaxy, 66, 67 Galaxy, 68, 74 Basical 80, 81, 82, 83+, 83 CE, 84+SE, 85, 86, 89, 89 titanium, 92, 95 Procalc, v200, nSpire cx
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Re: tri de listes
Sur HP Prime, la commande est SORT tout court. Mais une seule liste en argument oui.
Il y a bien plus de possibilités sur les listes avec les dernières calculatrices HP que chez TI :
CONCAT, REVERSE, POS, SIZE,
et on peut évoquer les commandes ASC et CHAR superbes pour traiter les lettres alphabétiques dans une liste (codage par exemple).
Il y a bien plus de possibilités sur les listes avec les dernières calculatrices HP que chez TI :
CONCAT, REVERSE, POS, SIZE,
et on peut évoquer les commandes ASC et CHAR superbes pour traiter les lettres alphabétiques dans une liste (codage par exemple).
News, programmes et aide calculatrices HP : http://mic.nic.free.fr
Le mode examen de la HP Prime pour le BAC
Dompter sa HP Prime en 10 minutes
Facebook - Twitter
Le mode examen de la HP Prime pour le BAC
Dompter sa HP Prime en 10 minutes
Facebook - Twitter
Re: tri de listes
Le bubble sort est raisonnable pour les petits tableaux, mais c'est un des tris quadratiques, il devient vite très lent en pratique quand la taille du tableau augmente.
Sur plate-forme embarquée, le shell sort peut être un bon choix (c'est ce que GCC4TI utilise, avec une amélioration par rapport à son prédécesseur), même si le shell sort est toujours de complexité dans le pire cas supérieure à n*log(n). Sinon, bien sûr, merge sort, quick sort (de préférence modifié pour améliorer le pire cas), etc. - Wikipedia t'en dira plus que moi
De meilleurs produits ne donnent pas nécessairement une part de marché dominante... c'est ainsi.
Sur plate-forme embarquée, le shell sort peut être un bon choix (c'est ce que GCC4TI utilise, avec une amélioration par rapport à son prédécesseur), même si le shell sort est toujours de complexité dans le pire cas supérieure à n*log(n). Sinon, bien sûr, merge sort, quick sort (de préférence modifié pour améliorer le pire cas), etc. - Wikipedia t'en dira plus que moi
De meilleurs produits ne donnent pas nécessairement une part de marché dominante... c'est ainsi.
Re: tri de listes
Bonsoir à tous
Je viens de tester le shell sort sur la Prime, par rapport au tri à bulles le temps est divisé par 2
(pour 1000 éléments), je peaufine tout ça et je vous transmet, merci Lionel
Salut Mic
A+.
Je viens de tester le shell sort sur la Prime, par rapport au tri à bulles le temps est divisé par 2
(pour 1000 éléments), je peaufine tout ça et je vous transmet, merci Lionel
Salut Mic
Un petit comparatif pourrait être sympa.Il y a bien plus de possibilités sur les listes avec les dernières calculatrices HP que chez TI :
A+.
Ti(s) 60, 62 Galaxy, 66, 67 Galaxy, 68, 74 Basical 80, 81, 82, 83+, 83 CE, 84+SE, 85, 86, 89, 89 titanium, 92, 95 Procalc, v200, nSpire cx
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Re: tri de listes
Hmm, seulement un facteur 2 ? Habituellement, la différence entre le bubble sort et le shell sort est plus importante que ça avec des tableaux de cette taille...
Peut-être que les particularités d'implémentation sur Prime font que le gros du temps est passé ailleurs que dans les comparaisons et le tri proprement dit (accès aux éléments de la liste, par exemple), et que chercher à optimiser le tri lui-même ne change pas grand chose.
Aussi, quelle variante du shell sort as-tu utilisée ? L'original était quadratique (c'est cette variante que GCC4TI utilisait à l'origine), des gens ont apporté des améliorations significatives, même s'il a été montré qu'aucune variante n*log(n) du shell sort ne peut exister;
Peut-être que les particularités d'implémentation sur Prime font que le gros du temps est passé ailleurs que dans les comparaisons et le tri proprement dit (accès aux éléments de la liste, par exemple), et que chercher à optimiser le tri lui-même ne change pas grand chose.
Aussi, quelle variante du shell sort as-tu utilisée ? L'original était quadratique (c'est cette variante que GCC4TI utilisait à l'origine), des gens ont apporté des améliorations significatives, même s'il a été montré qu'aucune variante n*log(n) du shell sort ne peut exister;
Re: tri de listes
L'algo que j'ai utilisé n'était en fait qu'un tri à bulles amélioré, je viens d'en trouvé un autre
et cette fois j'obtiens un facteur 15 environ soit 5 sec environ pour trier 1000 données et créer la liste d'index
contre 72 sec pour le tri à bulles donné dans le code sur la Prime.
Impressionnant.
Je code cela sur la 50g et je vous fournit les programmes.
et cette fois j'obtiens un facteur 15 environ soit 5 sec environ pour trier 1000 données et créer la liste d'index
contre 72 sec pour le tri à bulles donné dans le code sur la Prime.
Impressionnant.
Je code cela sur la 50g et je vous fournit les programmes.
Ti(s) 60, 62 Galaxy, 66, 67 Galaxy, 68, 74 Basical 80, 81, 82, 83+, 83 CE, 84+SE, 85, 86, 89, 89 titanium, 92, 95 Procalc, v200, nSpire cx
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Re: tri de listes
Bonsoir à tous
Voilà j'ai réécrit mes 2 fonctions en utilisant le shellshort, après quelques tests voici les
différences avec le tri à bulles.
temps pour 100 données sur la Prime: tri à bulles 0.529 sec , tri shell 0.309 sec
temps pour 1000 données sur la Prime: tri à bulles 72.5 sec , tri shell 5.2 sec
temps pour 100 données sur la 50g: tri à bulles 400 sec , tri shell 120 sec
Voici les codes pour ceux que cela intéresseraient:
pour la Prime:
Et pour la 50g:
Voilà, tant que j'y suis je vous propose une autre fonction qui permet de trier une liste de chaînes de caractères
par ordre de longueur et par ordre alphabétique, ainsi la liste {"avant","bal","col", "du","après"} donnera ->{"du",bal","col","après","avant"}
Pour l'algorithme, un code de caractère est calculé par rapport à la longueur de la chaîne, plus la chaîne est longue plus le code est grand
et donc plus le caractère de ce code est éloigné dans l'ordre alphabétique, ensuite on ajoute ce caractère de code calculé en tête de chaque chaîne,
puis les chaîne sont triées et enfin le caractère est oté pour retrouver nos chaînes d'origine.
Voici les codes:
pour la Prime:
pour la 50g:
et en Ti Basic:
Ici on a affaire à un programme car comme dit plus haut sortA, est une instruction qui modifie une variable donc
inutlisable dans une fonction: on doit donc transmettre au programme le nom de la variable globale qui contient la liste
entre guillemets -> sortal("nomvar").
Il serait peut-être intéressant d'écrire une fonction de tri shell en Ti basic pour disposer d'une fonction au lieu d'une instruction, cela pourrait
être plus pratique, en ce qui me concerne il me reste à adapter ces fonctions en Lua pour ma nspire dont la fonction sort intégrée souffre des mêmes
restrictions que celle des Hp.
A bientôt.
Voilà j'ai réécrit mes 2 fonctions en utilisant le shellshort, après quelques tests voici les
différences avec le tri à bulles.
temps pour 100 données sur la Prime: tri à bulles 0.529 sec , tri shell 0.309 sec
temps pour 1000 données sur la Prime: tri à bulles 72.5 sec , tri shell 5.2 sec
temps pour 100 données sur la 50g: tri à bulles 400 sec , tri shell 120 sec
Voici les codes pour ceux que cela intéresseraient:
pour la Prime:
Code : Tout sélectionner
Ecart(n)
BEGIN
LOCAL u;
WHILE u<n DO
u:=3*u+1;
END;
(u-1)/3;
END;
EXPORT SORTM(o)
BEGIN
LOCAL f,i,j,d,n;
LOCAL e,k,l,z,p,s;
IF TYPE(o[1])==6 THEN
l:=o[1];f:=1;
ELSE
l:=o;
END;
d:=SIZE(l);
k:=MAKELIST(I,I,1,d);
p:=Ecart(d);
WHILE p>0 DO
FOR i FROM p+1 TO d DO
e:={l[i],k[i]};
j:=i;s:=1;
WHILE j>p AND s DO
IF l[j-p]>e[1] THEN
l[j]:=l[j-p];k[j]:=k[j-p];
j:=j-p;
ELSE
s:=0;
END;
END;
l[j]:=e[1];k[j]:=e[2];
END;
p:=iquo(p,3);
END;
IF f THEN
o[1]:=l;n:=SIZE(o);
FOR i FROM 2 TO n DO
z:=SIZE(o[i]);l:={};
FOR j FROM 1 TO d DO
l[j]:=o(i,k[j]);
END;
o[i]:=IFTE(z>d,CONCAT(l,SUB(o[i],j,z)),l);
END;
o;
ELSE
{l,k};
END;
END;
Code : Tout sélectionner
<< 128. CF DUP 1. GET DUP TYPE
IF 5. ==
THEN 128. SF
ELSE DROP
END DUP SIZE 0. DUP2
WHILE >
REPEAT 3. * 1. + DUP2
END 1. - 3. / ROT
<< n
>> 'n' 1. 6. PICK 1. SEQ 0. -> d p l k j
<<
WHILE p
REPEAT p 1. + d
FOR i i 'j' STO 127. SF 'k' i GET 'l' i GET
WHILE j p > 127. FS? AND
REPEAT 'l' j p - GET
IF OVER >
THEN 'l' DUP j p - GET j SWAP PUT 'k' DUP j p - GET j SWAP PUT j p - 'j' STO
ELSE 127. CF
END
END 'l' j ROT PUT 'k' j ROT PUT
NEXT p 3. IQUOT 'p' STO
END
IF 128. FC?
THEN l k 2. ->LIST
ELSE 1. l PUT DUP SIZE 2. SWAP
FOR i { } SWAP DUP i GET 1. d
FOR j DUP k j GET GET 4. ROLL + UNROT
NEXT DUP SIZE d DUP2
IF >
THEN 1. + SWAP SUB REVLIST ROT + SWAP
ELSE 3. DROPN
END i ROT REVLIST PUT
NEXT
END
>>
>>
par ordre de longueur et par ordre alphabétique, ainsi la liste {"avant","bal","col", "du","après"} donnera ->{"du",bal","col","après","avant"}
Pour l'algorithme, un code de caractère est calculé par rapport à la longueur de la chaîne, plus la chaîne est longue plus le code est grand
et donc plus le caractère de ce code est éloigné dans l'ordre alphabétique, ensuite on ajoute ce caractère de code calculé en tête de chaque chaîne,
puis les chaîne sont triées et enfin le caractère est oté pour retrouver nos chaînes d'origine.
Voici les codes:
pour la Prime:
Code : Tout sélectionner
EXPORT SORTL(l)
BEGIN
LOCAL d,r;
SIZE(l)▶d;
SORT(MAKELIST(CHAR(DIM(l[I])+32)+l[I],I,1,d))▶r;
MID(r,2);
END;
Code : Tout sélectionner
<<
<< DUP SIZE 35 + CHR SWAP +
>> MAP SORT
<< TAIL
>> MAP
>>
Code : Tout sélectionner
sortal(v)
Prgm
Local d
dim(#v)->d
Seq(char(dim(#v[i])+35)&v[i],i,1,d)->#v
SortA #v
Seq(mid(#v[i],2),i,1,d)->#v
EndPrgm
inutlisable dans une fonction: on doit donc transmettre au programme le nom de la variable globale qui contient la liste
entre guillemets -> sortal("nomvar").
Il serait peut-être intéressant d'écrire une fonction de tri shell en Ti basic pour disposer d'une fonction au lieu d'une instruction, cela pourrait
être plus pratique, en ce qui me concerne il me reste à adapter ces fonctions en Lua pour ma nspire dont la fonction sort intégrée souffre des mêmes
restrictions que celle des Hp.
A bientôt.
Ti(s) 60, 62 Galaxy, 66, 67 Galaxy, 68, 74 Basical 80, 81, 82, 83+, 83 CE, 84+SE, 85, 86, 89, 89 titanium, 92, 95 Procalc, v200, nSpire cx
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Re: tri de listes
Bonsoir à tous
Voici aujourd'hui une instruction de tri pour le psion s3 en OPL.
OPL ne connaît pas les listes, mais les tableaux oui.
On ne peut transmettre un tableau à une procédure comme paramètre,
il faut donc en passer par son adresse, de plus la dimension d'un tableau doit être
connue dès le départ, on ne peut écrire par exemple:
on ne peut pas non plus renvoyé un tableau comme valeur de retour, adieu donc la fonction sort.
L'instruction sort que je vous propose permet de trier un tableau de flottants, et de faire suivre
le mouvement à un tableau d'entiers qui contient les index:
On fabriquera ce tableau d'entiers de la manière suivante :
On appelle la procédure sort en transmettant les 2 adresses des tableaux sous la forme ADDR(tab()),ADDR(tab%())
ou ADDR(tab(1)),ADDR(tab%(1)) ce qui revient au même et la dimension des 2 tableaux.
Un flottant est codé sur 8 octets, un entier sur 2, l'adresse d'un éléments est calculé par la formule
adresse tableau +( n° élément-1)*nombre d'octets, voilà pourquoi on soustrait 8 et 2 aux adresses de départ.
on utilise ensuite peek et poke pour lire et écrire les valeurs.
Le tableau d'index vous permet ensuite de ranger d'autres tableaux dans le même ordre que le tableau trié par sort.
Espérant que cela pourra vous être utile.
A+.
PS : petite question, pourquoi les variables nad1% et nad2% ont-elles été créées ?
Voici aujourd'hui une instruction de tri pour le psion s3 en OPL.
OPL ne connaît pas les listes, mais les tableaux oui.
On ne peut transmettre un tableau à une procédure comme paramètre,
il faut donc en passer par son adresse, de plus la dimension d'un tableau doit être
connue dès le départ, on ne peut écrire par exemple:
Code : Tout sélectionner
Proc start:
local n%=100
cretab:(n%)
...
...
Endp
Proc cretab:(d%)
global tab(n%)
....
....
Endp
L'instruction sort que je vous propose permet de trier un tableau de flottants, et de faire suivre
le mouvement à un tableau d'entiers qui contient les index:
On fabriquera ce tableau d'entiers de la manière suivante :
Code : Tout sélectionner
global i%(10),i%
do
i%=i%+1
i%(i%)=i%
until i%=10
ou ADDR(tab(1)),ADDR(tab%(1)) ce qui revient au même et la dimension des 2 tableaux.
Un flottant est codé sur 8 octets, un entier sur 2, l'adresse d'un éléments est calculé par la formule
adresse tableau +( n° élément-1)*nombre d'octets, voilà pourquoi on soustrait 8 et 2 aux adresses de départ.
on utilise ensuite peek et poke pour lire et écrire les valeurs.
Code : Tout sélectionner
PROC sort:(ad1%,ad2%,n%)
local e,e%,p%,i%,j%,s%,nad1%,nad2%
p%=ecart%:(n%)
nad1%=usub(ad1%,8) :nad2%=usub(ad2%,2)
while p%>0
i%=p%+1
do
e=peekf(uadd(nad1%,i%*8))
e%=peekw(uadd(nad2%,i%*2))
j%=i% :s%=-1
while j%>p% and s%
if peekf(uadd(nad1%,(j%-p%)*8)>e
pokef(uadd(nad1%,j%*8)),peekf(uadd(nad1%,(j%-p%)*8))
pokew(uadd(nad2%,j%*2)),peekw(uadd(nad2%,(j%-p%)*2))
j%=j%-p%
else
s%=0
endif
endwh
pokef(uadd(nad1%,j%*8)),e
pokew(uadd(nad2%,j%*2)),e%
i%=i%+1
until i%>n%
p%=p%/3
endwh
ENDP
PROC ecart%:(n%)
local u%
while u%<n%
u%=3*u%+1
endwh
return (u%-1)/3
ENDP
Espérant que cela pourra vous être utile.
A+.
PS : petite question, pourquoi les variables nad1% et nad2% ont-elles été créées ?
Ti(s) 60, 62 Galaxy, 66, 67 Galaxy, 68, 74 Basical 80, 81, 82, 83+, 83 CE, 84+SE, 85, 86, 89, 89 titanium, 92, 95 Procalc, v200, nSpire cx
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
-
- Fonctionne à 1200 bauds
- Messages : 580
- Enregistré le : 20 juin 2012 13:47
- Localisation : venelles 13770
Re: tri de listes
superbe boulot, bravo
Collection Apple
Apple //, //e, //c, Plus, SE, SE/30, Classic I, II, Color, IIci, IIsi, IIcx, II, IIfx, Quadra 700, LC, I, II, 475, PM 6400, 6500, 7600, 9600, G3 DT, G3 MTower, Cube, G4, G5, iMac G3, G4 15", G4 20" T, 20", 24" , 27" i7, MacPro .
MacPortable, PB Duo 2300C, iBook G3, G4 12" et 14", PB G4 12" et 15" Alu, 15" Ti, MB Pro CD 15", MBP 15", MBP 17", MBP 13".
IWriter I, II, StyleWriter I, II, QuickTake 100, Newtons, etc ...
Apple //, //e, //c, Plus, SE, SE/30, Classic I, II, Color, IIci, IIsi, IIcx, II, IIfx, Quadra 700, LC, I, II, 475, PM 6400, 6500, 7600, 9600, G3 DT, G3 MTower, Cube, G4, G5, iMac G3, G4 15", G4 20" T, 20", 24" , 27" i7, MacPro .
MacPortable, PB Duo 2300C, iBook G3, G4 12" et 14", PB G4 12" et 15" Alu, 15" Ti, MB Pro CD 15", MBP 15", MBP 17", MBP 13".
IWriter I, II, StyleWriter I, II, QuickTake 100, Newtons, etc ...
Re: tri de listes
Bonsoir
merci.
merci.
Ti(s) 60, 62 Galaxy, 66, 67 Galaxy, 68, 74 Basical 80, 81, 82, 83+, 83 CE, 84+SE, 85, 86, 89, 89 titanium, 92, 95 Procalc, v200, nSpire cx
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Re: tri de listes
Bonsoir à tous
Voici une version 89,92 de la fonction sortm, on fournit à la fonction
comme paramètres soit une liste et obtient 2 listes en retour : la liste fournie triée
+ une liste d'index pour trier d'autres listes ou bien une liste de listes et la première
liste est triée par ordre croissant et les autres suivent le mouvement.
Petite différence le Ti basic interprète une liste de listes comme une matrice, donc
les résultats sont une matrice, chaque liste devient une ligne, et les listes fournies doivent êtres toutes de même longueur,
sinon erreur.
Une grosse surprise le temps d'exécution pour trier une liste de 100 éléments <70 s
à comparer aux 120 secondes de la Hp 50g
Mon code pour Hp 50 ne doit pas être terrible, je sais qu'il y a quelques spécialistes parmi nous,
si ils daignent se manifester.
Voici une version 89,92 de la fonction sortm, on fournit à la fonction
comme paramètres soit une liste et obtient 2 listes en retour : la liste fournie triée
+ une liste d'index pour trier d'autres listes ou bien une liste de listes et la première
liste est triée par ordre croissant et les autres suivent le mouvement.
Petite différence le Ti basic interprète une liste de listes comme une matrice, donc
les résultats sont une matrice, chaque liste devient une ligne, et les listes fournies doivent êtres toutes de même longueur,
sinon erreur.
Code : Tout sélectionner
sortm(o)
Func
Local ecart
Define ecart(n)=Func
Local u
0->u
While u<n
u*3+1->u
EndWhile
(u-1)/3
EndFunc
Local f,i,j,d,n,e,k,l,p,s
If getType(o)="MAT" Then
mat>list(o[1])->l
1->f
Else
o->l:0->f
EndIf
dim(l)->d:seq(i,i,1,d)->k
ecart(d)->p
While p>0
For i,p+1,d
{l[i],k[i]}->e
i->j:1->s
While j>p and s>0
If l[j-p]>e[1] Then
l[j-p]->l[j]
k[j-p]->k[j]
j-p->j
Else
0->s
EndIf
EndWhile
e[1]->l[j]:e[2]->k[j]
EndFor
intDiv(p,3)->p
EndWhile
If f>0 Then
list>mat(l,d)->o[1]
rowDim(o)->n
For i,2,n
{}->l
For j,1,d
o[i,k[j]]->l[j]
EndFor
list>mat(l,d)->o[i]
EndFor
o
Else
{l,k}
EndIf
EndFunc
à comparer aux 120 secondes de la Hp 50g
Mon code pour Hp 50 ne doit pas être terrible, je sais qu'il y a quelques spécialistes parmi nous,
si ils daignent se manifester.
Ti(s) 60, 62 Galaxy, 66, 67 Galaxy, 68, 74 Basical 80, 81, 82, 83+, 83 CE, 84+SE, 85, 86, 89, 89 titanium, 92, 95 Procalc, v200, nSpire cx
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2936
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: tri de listes
Je viens de retrouver ce sujet suite à cette discussion sur la gazette 9.
Du coup voici une autre version du SORT multiple pour la HP Prime utilisant la capacité de la commande sort du CAS à trier des matrices ou des listes de listes en fonction d'un des éléments de la rangée. Ce n'est pas documenté sur la Prime mais c'est une fonction de xcas documentée en particulier sur cette page.
Extrait:
Il trie une ou plusieurs listes. Si les listes n'ont pas la même taille elles sont tronquées sur la taille de la plus courte.
Exemples:
Du coup voici une autre version du SORT multiple pour la HP Prime utilisant la capacité de la commande sort du CAS à trier des matrices ou des listes de listes en fonction d'un des éléments de la rangée. Ce n'est pas documenté sur la Prime mais c'est une fonction de xcas documentée en particulier sur cette page.
Extrait:
La fonction sort de Xcas effectue un tri par ordre croissant, d'une liste ou d'une séquence selon la fonction <. Si le premier argument est une liste, on peut passer en deuxième argument une fonction de tri, par exemple
sort([[4,2],[3,5],[5,6]], (x,y)-> x[0] > y[0] )
effectue un tri d'une matrice en utilisant la première composante de chaque ligne.
Code : Tout sélectionner
EXPORT SORTM(list0)
BEGIN
LOCAL n,m,o,list1,list2,list3,list4;
IF TYPE(list0)<>6 THEN RETURN list0; END;
n:=SIZE(list0);
list1:=MAKELIST(TYPE(list0(I)),I,1,n);
list2:=MAKELIST(SIZE(list0(I)),I,1,n);
m:=MIN(list2);o:=MAX(list2);
IF m=1 OR POS(list1,2) THEN RETURN(IFTE(o=1 OR POS(list1,2),CAS("sort(list0)"),list0));END;
list3:=MAKELIST(MAKELIST(list0(I,J),I,1,n),J,1,m);
list4:=CAS("sort(list3,(x,y)->(x[1])<(y[1]))");
RETURN MAKELIST(MAKELIST(list4(I,J),I,1,m),J,1,n);
END;
Exemples:
- SORTM({{"b","c","a"},{10,20,30,40,50}}) retourne -> {{"a","b","c"},{30,10,20}}
- SORTM({{20,10,30,40,50},{"b","c","a"}}) retourne -> {{10,20,30},{"c","b","a"}}
- SORTM({20,40,30,50,10}) retourne -> {10,20,30,40,50}
- SORTM({{"avant","bal","col","du","après"},{20,50,30,10,40}}) retourne -> {{"après","avant","bal","col","du"},{40,20,50,30,10}}
- SORTM({"avant","bal","col","du","après"}) retourne -> {"après","avant","bal","col","du"}
- SORTM({{"avant","bal","col","du","après"},10}) retourne ->{{"avant","bal","col","du","après"},10}
Re: tri de listes
Merci pour ce programme Zpalm.
Ti(s) 60, 62 Galaxy, 66, 67 Galaxy, 68, 74 Basical 80, 81, 82, 83+, 83 CE, 84+SE, 85, 86, 89, 89 titanium, 92, 95 Procalc, v200, nSpire cx
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07
Hp(s) 35s, 41CX, 28S, 48g, 50g, 39gII, Prime G1 et G2,
Casio(s) fx 602P, 702P, 4000P, 4500P, 6000G, 6900G, 7700G, 8500g, PB-700, CG-20, Graph 95 sd
Psion(s)II LZ64, siena, s3a, s3mx, s5mx.
Sharp(s) pc-1350, 1403, 1500A, E500, El 5120, 9200, 9600
Canon X-07