contrib/pep8analysis/tests/privat/07-tri2.pep

   1 ; Programme qui lit 10 entiers, les trie et les affiche
   2 ; (c) Jean Privat 2012
   3 ; Note: Ce programme essaye d'être aussi lisible que possible, donc aucune optimisation assembleur n'est faite
   4 ;
   5 ; progamme princial
   6 ; le programme est découpé en trois étapes : - la lecture ; 2 - le tri ; 3 - l'affichage.
   7 ; Théoriquement, le tri et l'afichage aurait pu etre fusionés, mais cela compexifie la lecture et le gain en performance est minime.
   8          CALL    lire        ;
   9          CALL    trier       ;
  10          CALL    ecrire      ;
  11          STOP
  12 tab:     .BLOCK  20          ; int[10] tab // #2d10a Tableau de 10 entiers (1 mot par entier)
  13 tablen:  .EQUATE 20          ; // taille du tableau (en octets)
  14 ;
  15 ;
  16 ;lire: lit les entiers de l'input et les range dans le tableau.
  17 ; l'algo utilise une simple boucle sur X pour lire toutes les cases
  18 lire:    LDX     0,i
  19 lire_bcl:CPX     tablen,i
  20          BRGE    lire_fin    ; for (X=0; X<tablen; X+=2) { // 2 car on compte les octets
  21          DECI    tab,x       ;   tab[X] = DECI();
  22          ADDX    2,i
  23          BR      lire_bcl    ; } // fin for
  24 lire_fin:RET0                ; return;
  25 ;
  26 ;
  27 ;ecrire: ecrit les entiers du tableau sur l'output en les séparants par des espaces et en terminant la ligne par un retour chariot.
  28 ; l'algo utilise une simple boucle sur X pour écrire toutes les cases
  29 ecrire:  LDX     0,i
  30 ecri_bcl:CPX     tablen,i
  31          BRGE    ecri_fin    ; for (X=0; X<tablen; X+=2) { // 2 car on compte les octets
  32          DECO    tab,x
  33          CHARO   ' ',i       ;   print(tab[X], ' ');
  34          ADDX    2,i
  35          BR      ecri_bcl    ; } // fin for
  36 ecri_fin:CHARO   '\n',i
  37          RET0                ; return;
  38 ;
  39 ;
  40 ;trier: trie par permutation du tableau.
  41 ; l'algo utilise deux boucles impriquées
  42 trier:   LDX     0,i
  43          STX     i,d
  44 tri_bcl1:LDX     i,d
  45          CPX     tablen,i
  46          BRGE    trie_fin    ; for(i=0; i<tablen; i+=2) { // grande boucle
  47 ;                            ;   // l'objectif de cette grande boucle est de mettre dans tab[i] le plus petit element restant
  48 ;                            ;   // l'invariant de boucle est que les éléments avant i sont déjà bien placés (triés)
  49 ;
  50          LDX     i,d
  51          ADDX    2,i
  52          STX     j,d
  53 tri_blc2:LDX     j,d
  54          CPX     tablen,i
  55          BRGE    blc2_fin    ;   for(j=i+2; j<tablen; j+=2) { // petite boucle
  56 ;                            ;     // l'objectif de cette petite boucle est de chercher via tab[j] le plus petit élément restant
  57 ;                            ;     // l'invariant de boucle est que tout élément entre i et j est plus grand que tab[i]
  58          LDX     i,d
  59          LDA     tab,x
  60          LDX     j,d
  61          CPA     tab,x
  62          BRLE    noswitch    ;     if (tab[i] > tab[j]) {
  63 ;                            ;       // pour respecter l'ordre, il faut inverser tab[i] et tab[j]
  64          LDX     i,d
  65          LDA     tab,x
  66          STA     tmp,d       ;       tmp = tab[i];
  67          LDX     j,d
  68          LDA     tab,x
  69          LDX     i,d
  70          STA     tab,x       ;       tab[i] = tab[j];
  71          LDA     tmp,d
  72          LDX     j,d
  73          STA     tab,x       ;       tab[j] = tmp;
  74 noswitch:NOP0                ;     } // fin if
  75 ;
  76          LDX     j,d
  77          ADDX    2,i
  78          STX     j,d
  79          BR      tri_blc2
  80 blc2_fin:NOP0                ;   } // fin boucle j (cat j+=2)
  81 ;
  82          LDX     i,d
  83          ADDX    2,i
  84          STX     i,d
  85          BR      tri_bcl1    ; } // fin boucle i (cad i+=2)
  86 ;
  87 trie_fin:RET0                ; return;
  88 ; variables utiliées par la fonction `trier':
  89 i:       .BLOCK  2           ; indice de la grande boucle
  90 j:       .BLOCK  2           ; indice de la petite boucle
  91 tmp:     .BLOCK  2           ; valeur temporaire pour la permutation
  92 ;
  93          .END