knuta
C KNUTA SOURCE CHAT 05/01/13 00:58:29 5004 C C C C *************************************************************** C OBJET : TRI UN TABLEAU D'ENTIERS DANS L'ORDRE CROISSANT C TRI PAR INCREMENT DECROISSANT (SHELL SORTING - KNUTH 1973) C C ON TRIE LES N TERMES NARG(I) POUR I=1,N C C TRI PAR INCREMENT DECROISSANT (SHELL SORTING) C COMPLEXITE EN N PUISSANCE 3/2 ET MEME STATISTIQUEMENT EN N**1.2 C C POUR EN SAVOIR PLUS : KNUTH, "THE ART OF COMPUTER PROGRAMMING", C VOL 3 : SORTING AND SEARCHING, C ADDISON-WESLEY, 1973. C C KNUTA : A COMME ACTIF, C.A.D. QUE LES ARGUMENTS NARG(I) POUR C I=1 A N SONT PHYSIQUEMENT "PERMUTES" (TABLEAU NARG MODIFIE). C VOIR AUSSI KNUTP. C C C REMARQUE : NARG PEUT ETRE DE TOUT TYPE ET TOUTE LOI D'ORDRE C PEUT ETRE INTRODUITE. IL SUFFIT D'INTERVENIR C AUX ENDROITS INDIQUES AINSI : '***** ICI : ...'. C C *************************************************************** IMPLICIT INTEGER(I-N) INTEGER N,NARG(*) INTEGER NARGJ INTEGER I,J,K,INCR C C ON N'A RIEN A TRIER C IF(N.LE.1) GOTO 9999 C C POUR J=INCR+1,N, LA SOUS-SUITE NARG(J+H*INCR), H=...,-3,-2,-1,0 C SERA ORDONNEE (TRI HABITUEL PAR INSERTION SEQUENTIELLE). C C DES QUE INCR=1 ON A ATTEINT L'OBJECTIF FINAL. C C INCR SUBIT UNE DECROISSANCE PROGRESSIVE DE SORTE QU'AU C DEBUT IL EST GRAND (LA SOUS-SUITE A TRIER A UN CARDINAL FAIBLE) C ENSUITE QUAND INCR DIMINUE LA PROFONDEUR DES PERMUTATIONS C NECESSAIRES RESTE LIMITEE GRACE AU TRI DE LA SOUS-SUITE C CORRESPONDANT A LA VALEUR PRECEDENTE DE L'INCREMENT (LE PAS). C INCR=N C C DECROISSANCE DE L'INCREMENT PAR DIVISION PAR 2 C 10 INCR=INCR/2 C C POUR TOUT J VARIANT DE INCR+1 A N, C LA SOUS-SUITE NARG(J+H*INCR) AVEC H=...,-3,-2,-1,0 C SERA ORDONNEE. C DO 40 J=INCR+1,N C C ON PROCEDE PAR RECURENCE : LE FAIT QUE LES ELEMENTS C NARG(J+H*INCR) DEPUIS LE DEBUT JUSQU'A J+H*INCR=K-INCR C SOIENT DEJA ORDONNES EST UTILISE POUR ALLER JUSTE PLACER C CONVENALEMENT L'ELEMENT NARG(K) : INSERTION SEQUENTIELLE. C C C ***** ICI : SAUVEGARDE DE NARG(J) C NARGJ=NARG(J) K=J DO 20 I=J-INCR,1,-INCR C C ***** ICI : LOI D'ORDRE C COMPARER NARG(I) ET NARGJ=NARG(J) C SI NARG(I) EST AVANT OU EGAL A NARGJ ALLER EN 30 C IF(NARG(I).LE.NARGJ) GOTO 30 C C ***** ICI : AFFECTER LE CONTENU DE NARG(I) A NARG(K) C NARG(K)=NARG(I) K=I 20 CONTINUE C C ***** ICI : AFFECTER LE CONTENU DE NARGJ A NARG(K) C 30 NARG(K)=NARGJ C C FIN DU TRI DE LA SOUS-SUITE ASSOCIEE A J C 40 CONTINUE C C PEUT-ON ENCORE DIMINUER L'INCREMENT (LE PAS) ? C IF(INCR.GT.1) GOTO 10 C C INCR=1, LE TRI FINAL EST ACHEVE. MERCI DE VOTRE VISITE. C 9999 END
© Cast3M 2003 - Tous droits réservés.
Mentions légales