Télécharger ordm04.eso

Retour à la liste

Numérotation des lignes :

  1. C ORDM04 SOURCE JC220346 14/12/16 21:15:05 8324
  2. ************************************************************************
  3. * NOM : ORDM04
  4. * DESCRIPTION : Tri par fusion (Merge Sort) pour une liste d'entiers
  5. * On renvoie en plus le nouvel ORDRE des elements
  6. ************************************************************************
  7. * APPELE PAR : pilot.eso
  8. ************************************************************************
  9. * ENTREES :: A = liste d'entiers a trier
  10. * AI = rang des elements de A (entiers de 1 a N)
  11. * N = longueur des listes A et AI
  12. * T = tableau de travail d'entiers de longueur (N+1)/2
  13. * TI = tableau de travail d'entiers de longueur (N+1)/2
  14. * CROISS = booleen indiquant l'ordre du tri
  15. * SORTIES :: A = liste triee
  16. * AI = position initiale des elements de la liste triee
  17. ************************************************************************
  18. RECURSIVE SUBROUTINE ORDM04(A,AI,N,T,TI,CROISS)
  19. *
  20. INTEGER I,J,K,N,NA,NB,A,T,V,AI,TI,VI
  21. DIMENSION A(N),AI(N),T((N+1)/2),TI((N+1)/2)
  22. LOGICAL CROISS,DECROI
  23. *
  24. * On arrete la recursion pour N=1 ou N=2
  25. IF (N.LT.2) RETURN
  26. DECROI = .NOT.CROISS
  27. IF (N.EQ.2) THEN
  28. IF ((CROISS.AND.A(1).GT.A(2)).OR.
  29. & (DECROI.AND.A(1).LT.A(2))) THEN
  30. V = A(1)
  31. A(1) = A(2)
  32. A(2) = V
  33. VI = AI(1)
  34. AI(1) = AI(2)
  35. AI(2) = VI
  36. ENDIF
  37. RETURN
  38. ENDIF
  39. *
  40. * Sinon, on subdivise en deux sous-listes plus petites que l'on
  41. * va ordonner separement
  42. NA=(N+1)/2
  43. NB=N-NA
  44. CALL ORDM04(A,AI,NA,T,TI,CROISS)
  45. CALL ORDM04(A(NA+1),AI(NA+1),NB,T,TI,CROISS)
  46. *
  47. * On melange les deux petites sous-listes en une grande liste
  48. * ordonnee (avec un peu de chance, il n'y a rien a faire...)
  49. IF ((CROISS.AND.A(NA).GT.A(NA+1)).OR.
  50. & (DECROI.AND.A(NA).LT.A(NA+1))) THEN
  51. T(1:NA)=A(1:NA)
  52. TI(1:NA)=AI(1:NA)
  53. I = 1
  54. J = 1
  55. K = 1
  56. DO WHILE (I.LE.NA.AND.J.LE.NB)
  57. V = A(NA+J)
  58. VI = AI(NA+J)
  59. IF ((CROISS.AND.T(I).LE.V).OR.
  60. & (DECROI.AND.T(I).GE.V)) THEN
  61. A(K) = T(I)
  62. AI(K) = TI(I)
  63. I = I+1
  64. ELSE
  65. A(K) = V
  66. AI(K) = VI
  67. J = J+1
  68. ENDIF
  69. K = K + 1
  70. ENDDO
  71. *
  72. DO WHILE (I.LE.NA)
  73. A(K) = T(I)
  74. AI(K) = TI(I)
  75. I = I + 1
  76. K = K + 1
  77. ENDDO
  78. ENDIF
  79. *
  80. RETURN
  81. *
  82. END
  83. *
  84.  

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