Suiv.: Aides à l'implémentation Sup.: 7 Programmes internes Préc.: 7.6 Manipulations de matrices et vecteurs Index Table des matières

7.7 Tris et dichotomies

De nombreuses subroutines de tri  sont proposées. Leurs différences résident dans le type et le nombre des paramètres d'entrée. Elles possèdent toutes 'HEAP' dans leurs noms sauf BUBBLE. Les *HEAP* sont des tris en O(log n), BUBBLE est en O(n**2).

      SUBROUTINE BUBBLE(TAB,N)
      INTEGER N,TAB(N)

Tri TAB par  valeur croissantes (BUBBLE-SORT).

      SUBROUTINE HEAP(CRITER, RECORD, N)
      INTEGER N, RECORD(N)
      REAL CRITER(N)

Tri selon les  valeurs de CRITER croissantes, RECORD suit le réordonnancement.

      SUBROUTINE HEAP2I(CRITER, N)
      INTEGER N
      INTEGER CRITER(2, N)

Tri selon les  valeurs de CRITER(1, *) croissantes. CRITER(2, *) suit le réordonnancement.

      SUBROUTINE HEAP3I(CRITER, N)
      INTEGER N
      INTEGER CRITER(3, N)

Tri selon les  valeurs de CRITER(1, *) croissantes CRITER(2, *) et CRITER(3, *) suivent le réordonnancement.

      SUBROUTINE HPD2I(CRITER, RECORD, N)
      INTEGER N, RECORD(2, N)
      DOUBLE PRECISION CRITER(N)

Tri selon les  valeurs de CRITER croissantes. RECORD suit le réordonnancement.

      SUBROUTINE HEAPDI(CRITER, RECORD, N)
      INTEGER N, RECORD(N)
      DOUBLE PRECISION CRITER(N)

Tri selon les  valeurs de CRITER croissantes. RECORD suit le réordonnancement.

      SUBROUTINE HEAPI(CRITER, N)
      INTEGER N
      INTEGER CRITER(N)

Tri selon les  valeurs de CRITER croissantes.

      SUBROUTINE HEAPI2(CRITER, RECORD, N)
      INTEGER N, RECORD(N)
      INTEGER CRITER(N)

Tri selon les  valeurs de CRITER croissantes. RECORD suit le réordonnancement.

      SUBROUTINE HEPI2I(CRITER, RECORD, N)
      INTEGER N, RECORD(2, N)
      INTEGER CRITER(N)

Tri selon les  valeurs de CRITER croissantes. RECORD suit le réordonnancement.

      SUBROUTINE HEAPI3(CRITER, RECRD1, RECRD2, RECRD3, N)
      INTEGER N
      INTEGER RECRD1(N), RECRD2(N), RECRD3(N)
      INTEGER CRITER(N)

Tri selon les  valeurs de CRITER croissantes. RECRD* suivent le réordonnancement.

      SUBROUTINE DHEAP(CRITER,RECORD,N)
      INTEGER N,RECORD(N)
      DOUBLE PRECISION CRITER(N)

Tri selon les  valeurs de CRITER croissantes RECORD suit le réordonnancement.

      SUBROUTINE HPLX2I(CRITER, N)
      INTEGER N
      INTEGER CRITER(2, N)

Tri lexicographique selon les  valeurs de CRITER(1, *) et CRITER(2, *) croissantes.

      SUBROUTINE HPLX2R(CRITER, RECORD, N)
      INTEGER N
      REAL CRITER(2, N)
      INTEGER RECORD(N)

Tri lexicographique selon les  valeurs de CRITER(1, *) et CRITER(2, *) croissantes.

      SUBROUTINE HPLXNI(CRITER, MM, N)
      INTEGER N, MM
      INTEGER CRITER(MM, N)

Tri lexicographique selon les  valeurs de CRITER(1, *), CRITER(2, *) ... CRITER(MM, *) croissantes.

      SUBROUTINE HPLXNR(CRITER, MM, N)
      INTEGER N, MM
      REAL CRITER(MM, N)

Tri lexicographique selon les  valeurs de CRITER(1, *), CRITER(2, *), ... CRITER(MM, *) croissantes.

      INTEGER FUNCTION IDICHO(CRIT, N, VAL)
      INTEGER N
      INTEGER CRIT(N), VAL

Recherche par dichotomie  de la  valeur VAL dans CRIT.

CRIT est supposé avoir été trié en ordre croissant.

Entrée: CRIT, N, VAL

Sortie: IDICHO = Index dans CRIT si on a trouvé à encadrer VAL :

= 0 si VAL < CRIT(1)

= N si VAL > CRIT(N)

On a la relation:

CRIT(IDICHO(CRIT, N, VAL)) VAL < CRIT(IDICHO(CRIT, N, VAL)+1)

      INTEGER FUNCTION DICHOI(CRIT, N, VAL)
      INTEGER N
      INTEGER CRIT(N), VAL

Recherche par dichotomie  de la  valeur VAL dans CRIT.

CRIT est supposé avoir été trié en ordre croissant.

Entrée: CRIT, N, VAL

Sortie: DICHOI = Index dans CRIT si on a trouvé la valeur VAL :

= 0 si VAL n'a pas été trouvé

      INTEGER FUNCTION DICHO(CRIT, N, VAL)
      INTEGER N
      REAL CRIT(N), VAL

Recherche par dichotomie de la  valeur VAL dans CRIT

CRIT est supposé avoir été trié en ordre croissant.

Entrée: CRIT, N, VAL

Sortie: DICHO = index dans CRIT si on a trouvé à encadrer VAL.

=0 si VAL < CRIT(1)

=N si VAL > CRIT(N)

On a la relation:

CRIT(DICHO(CRIT, N, VAL)) VAL < CRIT(DICHO(CRIT, N, VAL)+1)