Télécharger knuta.eso

Retour à la liste

Numérotation des lignes :

  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