Esope source files

   1 : C KNUTA     SOURCE    CHAT      05/01/13    00:58:29     5004           
   2 : C
   3 : C
   4 : C
   5 :       SUBROUTINE KNUTA(N,NARG)
   6 : C     ***************************************************************
   7 : C     OBJET : TRI UN TABLEAU D'ENTIERS DANS L'ORDRE CROISSANT
   8 : C          TRI PAR INCREMENT DECROISSANT (SHELL SORTING - KNUTH 1973)
   9 : C
  10 : C     ON TRIE LES N TERMES NARG(I) POUR I=1,N
  11 : C
  12 : C     TRI PAR INCREMENT DECROISSANT (SHELL SORTING)
  13 : C     COMPLEXITE EN N PUISSANCE 3/2 ET MEME STATISTIQUEMENT EN N**1.2
  14 : C
  15 : C     POUR EN SAVOIR PLUS : KNUTH, "THE ART OF COMPUTER PROGRAMMING",
  16 : C                           VOL 3 : SORTING AND SEARCHING,
  17 : C                           ADDISON-WESLEY, 1973.
  18 : C
  19 : C     KNUTA : A COMME ACTIF, C.A.D. QUE LES ARGUMENTS NARG(I) POUR
  20 : C             I=1 A N SONT PHYSIQUEMENT "PERMUTES" (TABLEAU NARG MODIFIE).
  21 : C             VOIR AUSSI KNUTP.
  22 : C
  23 : C
  24 : C     REMARQUE : NARG PEUT ETRE DE TOUT TYPE ET TOUTE LOI D'ORDRE
  25 : C                PEUT ETRE INTRODUITE. IL SUFFIT D'INTERVENIR
  26 : C                AUX ENDROITS INDIQUES AINSI : '***** ICI : ...'.
  27 : C
  28 : C     ***************************************************************
  29 :       IMPLICIT INTEGER(I-N)
  30 :       INTEGER N,NARG(*)
  31 :       INTEGER NARGJ
  32 :       INTEGER I,J,K,INCR
  33 : C
  34 : C     ON N'A RIEN A TRIER
  35 : C
  36 :       IF(N.LE.1) GOTO 9999
  37 : C
  38 : C     POUR J=INCR+1,N, LA SOUS-SUITE NARG(J+H*INCR), H=...,-3,-2,-1,0
  39 : C     SERA ORDONNEE (TRI HABITUEL PAR INSERTION SEQUENTIELLE).
  40 : C
  41 : C     DES QUE INCR=1 ON A ATTEINT L'OBJECTIF FINAL.
  42 : C
  43 : C     INCR SUBIT UNE DECROISSANCE PROGRESSIVE DE SORTE QU'AU
  44 : C     DEBUT IL EST GRAND (LA SOUS-SUITE A TRIER A UN CARDINAL FAIBLE)
  45 : C     ENSUITE QUAND INCR DIMINUE LA PROFONDEUR DES PERMUTATIONS
  46 : C     NECESSAIRES RESTE LIMITEE GRACE AU TRI DE LA SOUS-SUITE
  47 : C     CORRESPONDANT A LA VALEUR PRECEDENTE DE L'INCREMENT (LE PAS).
  48 : C
  49 :       INCR=N
  50 : C
  51 : C     DECROISSANCE DE L'INCREMENT PAR DIVISION PAR 2
  52 : C
  53 :    10 INCR=INCR/2
  54 : C
  55 : C     POUR TOUT J VARIANT DE INCR+1 A N,
  56 : C     LA SOUS-SUITE NARG(J+H*INCR) AVEC H=...,-3,-2,-1,0
  57 : C     SERA ORDONNEE.
  58 : C
  59 :       DO 40 J=INCR+1,N
  60 : C
  61 : C       ON PROCEDE PAR RECURENCE : LE FAIT QUE LES ELEMENTS
  62 : C       NARG(J+H*INCR) DEPUIS LE DEBUT JUSQU'A J+H*INCR=K-INCR

  63 : C       SOIENT DEJA ORDONNES EST UTILISE POUR ALLER JUSTE PLACER
  64 : C       CONVENALEMENT L'ELEMENT NARG(K) : INSERTION SEQUENTIELLE.
  65 : C
  66 : C
  67 : C         ***** ICI :  SAUVEGARDE DE NARG(J)
  68 : C
  69 :         NARGJ=NARG(J)
  70 :         K=J
  71 : 

Notice:  Undefined offset: 1 in C:\xampp\htdocs\cast3m_kit_local_fr_en_2014\sources.php on line 158



Notice:  Undefined offset: 1 in C:\xampp\htdocs\cast3m_kit_local_fr_en_2014\sources.php on line 158



Notice:  Undefined offset: 1 in C:\xampp\htdocs\cast3m_kit_local_fr_en_2014\sources.php on line 158

        DO 20 I=J-INCR,1,-INCR

  72 : C
  73 : C         ***** ICI :  LOI D'ORDRE
  74 : C         COMPARER NARG(I) ET NARGJ=NARG(J)
  75 : C         SI NARG(I) EST AVANT OU EGAL A NARGJ ALLER EN 30
  76 : C
  77 :           IF(NARG(I).LE.NARGJ) GOTO 30
  78 : C
  79 : C         ***** ICI :  AFFECTER LE CONTENU DE NARG(I) A NARG(K)
  80 : C
  81 :           NARG(K)=NARG(I)
  82 :           K=I
  83 :    20   CONTINUE
  84 : C
  85 : C         ***** ICI :  AFFECTER LE CONTENU DE NARGJ A NARG(K)
  86 : C
  87 :    30   NARG(K)=NARGJ
  88 : C
  89 : C       FIN DU TRI DE LA SOUS-SUITE ASSOCIEE A J
  90 : C
  91 :    40 CONTINUE
  92 : C
  93 : C     PEUT-ON ENCORE DIMINUER L'INCREMENT (LE PAS) ?
  94 : C
  95 :       IF(INCR.GT.1) GOTO 10
  96 : C
  97 : C     INCR=1, LE TRI FINAL EST ACHEVE. MERCI DE VOTRE VISITE.
  98 : C
  99 :  9999 END
 100 :  
 101 :