Télécharger la plaquette Cast3M


fr en

Télécharger knuta.eso

Retour à la liste

Numérotation des lignes : 

knuta

  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.         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.  
  102.  

© Cast3M 2003 - Tous droits réservés.
Mentions légales