> Cours > Informatique> Algorithmique et Analyse > Les tris simples

3. Les tris simples

3.1. Durées d'exécution

Avec l'étude des algorithmes de tri, nous allons être confrontés au problème des durées d'exécution qui varient énormément, selon l'algorithme choisi, lorsque le nombre de données traitées devient important.

1 heure = 3,6 103 secondes, 1 jour = 8,64 104 secondes, 1 an ≈ 3,2 107 secondes

232 ≈ 4,3 10 9, il faut un peu plus d'une heure pour effectuer 232 opérations, à raison d'une opération par micro-seconde, 
et pour imprimer ces résultats (un résultat par ligne, 300 lignes par minute) sur l'imprimante du LEI il faudrait environ 27 ans... 
et combien de temps pour les lire?

Autres valeurs remarquables : c'est à 31 ans qu'on atteint l'àge de 109 secondes et c'est en 1901 que l'ère chrétienne a eu 
109 minutes.

Enfin, on estime à 10120 le nombre de coups possibles au jeu d'échecs, si les 1075(?) particules de l'Univers étaient autant
d'ordinateurs il faudrait quelque 1030 millénaires pour trouver la stratégie gagnante (à propos, quel est l'âge de l'Univers?).

3.1.1. Croissance avec n

Nous avons représenté la variation des durées d'exécution de programmes en fonction du nombre n des éléments traités pour les lois de dépendance les plus communes : n², n log(n), n, log(n) ; les cœfficients numériques 2, 100, 200 et 500 ont été choisis arbitraitement, on observe que leur influence est faible devant celle de la loi de variation (c.-à-d., devant le type d'algorithme choisi).

3.1.2. Notations O, Θ et Ω

Comme nous venons de l'observer en considérant le graphique, l'influence des cœfficients numériques n'est pas le critère le plus important lorsque croît le nombre n des données à traiter, c'est principalement la loi (n², n log(n), n...) qui détermine la croissance de la durée d'exécution. C'est ce qui est représenté par les notations Θ, O, etc. On notera, par exemple, qu'un algorithme a une complexité temporelle en Θ(n²), ou encore en O(n²) ou Ω(n²). La signification de ces symboles n'est pas toujours précisée¹.

Considérons f et g, deux fonctions de n à valeurs positives. On dira que f croît comme Θ(g) si il existe deux constantes c₁ et c₂ positives et une valeur n₀ telles que pour tout n > n₀ on ait c₁ g(n) f(n) c₂ g(n). On peut dire que f et g ont même ordre de grandeur asymptotique.

On dira que f croît comme O(g) si il existe une constante c positive et une valeur n₀ telles que pour tout n > n₀ on ait f(n) c g(n). On peut dire que f est dominée asymptotiquement par g. (Il faut se souvenir que la notation O est très souvent employée à la place de Θ).

La notation Ω correspond à la minoration asymptotique ; avec les mêmes hypothèses : c g(n) f(n).

Il faut noter qu'il existe dans ce domaine encore d'autres notations : o, ω.

3.2. Trier

"Trier 1° Choisir parmi d'autres; extraire d'un plus grand nombre après examen [...].
2° Séparer, dans un ensemble (un certain nombre de choses homogènes) d'avec ce qui était mêlé [...].
3° Répartir (un ensemble de choses) en plusieurs groupes sans rien éliminer [...]."
le petit Robert

Aucune de ces définitions ne correspond à l'usage de ce mot en informatique, qui serait plutôt "classer selon un ordre donné" (valeurs croissantes, ordre lexicographique, etc...). Il semble que l'origine vienne des "trieuses", machines mécanographiques qui permettaient de répartir des cartes perforées (support d'information prédominant jusqu'à il y a une vingtaine d'années) dans différentes cases, cette répartition étant déterminée par la perforation d'une colonne choisie. La figure ci-dessous illustre comment on pouvait ainsi "trier" un paquet de cartes en fonction des valeurs figurant dans des colonnes déterminées.

Remarques :

• dans ce chapitre sur les tris, tous les objets à trier sont rangés en tableaux,
• on ne traitera que de tris croissants, c.-à-d. que, après le tri, tous les éléments du tableau trié vérifient la relation : t(k) < t(k+1) (ou t(k) t(k+1) si on admet la possibilité d'éléments égaux),
• on est aussi amené à discuter de la stabilité d'un algorithme de tri : on dira qu'un tri est stable si pour toutes les paires d'éléments égaux : t(k) = t(k') avec (k < k' avant le tri) l'élément t(k) occupe après tri une position p et l'élément t(k') une position p' qui vérifie p < p' (l'ordre de rangement initial d'éléments de valeurs égales est conservé).
• les spécifications externes d'une procédure de tri sont très simples : on lui passe un tableau t de n éléments, elle doit rendre le même tableau trié. L'en-tête de toutes les procédures sera uniforme :
  

  procédure tri_>xx (t : tableau de ty_el_tri indice [1..n],              Entrée/Sortie /* tableau à */
                     n : numérique,                                       Entrée /* nombre d'éléments à trier */)

  La nature exacte du type de ty_el_tri est de peu d'importance. Noter que, selon les langages, la valeur de n nécessite d'être passée explicitement ou peut-être passée explicitement ou peut-être connue implicitement.

Nous allons examiner quelques algorithmes simples qui répondent à ces spécifications.

3.3. Tri par sélection

3.3.1. Principe

C'est très simple, soit un tableau dont on veut trier les éléments (par valeurs croissantes), on recherche dans tout le tableau l'élément de plus petite valeur et on l'échange avec l'élément à la première place, on réitère ensuite pour le tableau privé du premier élément, puis pour le tableau privé de ses deux premièrs éléments, et ainsi de suite.

3.3.2. Mise en œuvre

Etape 0, systématisons le principe :

On suppose que la procédure de tri a déjà commencé de fonctionner et que l'on a séparé le tableau² t[1..n] en deux sous-tableaux t[1..place-1] et t[place..n] ; le sous-tableau t[1..place-1] est ordonné et contient les place-1 plus petits éléments de t[1..n]. On a donc : t(1) t(2) ... t(place-1) t[place..n].

On sélectionne l'élément de plus petite valeur du sous-tableau t[place..n] et on l'amène par échange à t(place). On a donc :

t(1) t(2) ... t(place-1) t(place) t[place+1..n]

Etape 1, recherche, et mise en place, de l'élément de valeur minimale³ de t[place..n] :

variables entières :
    k       /* indice pour l'exploration du sous-tableau t[place..n] */
    kmin    /* indice pointant vers l'élément de valeur minimale */

kmin  place
répéter pour k variant de place+1 à n
    si t(k) < t(kmin) alors      attention au choix de l'inégalité < ou  : on choisit, en général, de ne déplacer l'élément
        kmin  k         que si il est indispensable qu'il soit déplacé pour que la relation t(k)  t(k+1) soit vérifiée.
    fin_si
fin_répéter

 échanger (t(kmin), t(place))

Etape 2, réitération pour tous les éléments :

variables entières : place /* indice d'exploration : premier élément non encore cléss du tableau [1..n] */
répéter pour place variant de 1 à n-1
variables entières : k       /* indice pour l'exploration du sous-tableau t[place..n] */
                     kmin    /* indice pointant vers l'élément de valeur minimale */
    kmin  place
    répéter pour k variant de place+1 à n
        si t(k) < t(kmin) alors
            kmin  k
        fin_si
    fin_répéter
    échanger (t(kmin), t(place))
fin_répéter

Etape 3, mise en forme de la procédure^4,5 :

procédure tri_sélection (     t:      tableau de ty_el_tri indice [1..n],     Entrée/Sortie    /* tableau à trier/trié */ ;
                              n :     numérique,                              Entrée           /* nombre d'élément à trier */ ;
            placer ici ce qui a été défini à l'étape 2
fin_procédure tri_sélection

3.3.3. Complexité, stabilité

Il faut dénombrer les opérations élémentaires (à noter que toutes les comparaisons font intervenir un calcul d'adresse dans un tableau) :

• dans la première étape : n - place comparaisons, 1 échange
• dans la seconde étape : n (n - 1) / 2 comparaisons, la complexité temporelle est donc de Θ(n²), il y a n - 1 échanges, complexité temporelle Θ(n). (Remarquons que le nombre d'opérations est indépendant de l'ordre initial des éléments du tableau.)

Contrairement à ce qu'on pourrait penser, ce tri n'est pas stable : la procédure appliquée au tableau (3, 2, 3, 1) le montre sans peine.

3.4. Tri par insertion directe (tri du joueur de cartes)

3.4.1. Principe

Soit un tableau d'éléments à trier t[1..n] ; on suppose que le sous-tableau t[1..nt] est déjà trié (c.-à-d. t(k) t(k+1) quelque soit k dans [1..nt-1]) On considère l'élément t(nt+1) et on cherche à l'insérer à la bonne place dans le sous-tableau t[1..nt+1]. Pour cela deux étapes :

• déterminer la valeur de "place" telle que⁶ t(place-1) t(nt+1) < t(place)

  6. Ici encore, le choix des inégalités < ou est crucial pour la stabilité du tri.

  fermer cette précision

• insérer l'élément t(nt+1) en reculant, le cas échéant, les éléments du sous-tableau t[place..nt]

3.4.2. Déterminer la place (où insérer) par recherche séquentielle

Pour cela on procède comme un joueur de cartes range sa "main" : quand il a déjà rangé un certain nombre de cartes, il compare la nouvelle carte à la dernière (la plus forte) des cartes déjà rangées :

• si la nouvelle carte est plus forte que la dernière, il doit ranger la nouvelle carte derrière la dernière,
• sinon il la compare à l'avant-dernière, etc...

Finalement la place de la nouvelle carte est derrière la première carte rencontrée de valeur plus faible (ou de valeur égale, si une telle situation est possible) ; la position "place" de la carte de valeur "x" vérifie : t(place-1) x < t(place)

L'algorithme est immédiat :

x  t (nt+1)
place  nt+1
répéter      /* tant que la condition t(place-1)  x < t(place) n'est pas vérifiée */
    tant que place > 1      /* et tant qu'on peut */
    jusqu'à t(place-1)  x
        décrémenter (place)
fin_répéter

Compléxité : si la tableau d'origine t[1..nt] est déjà ordonné, la détermination de la place d'un nouvel élément ne demande qu'une comparaison ; par contre, si le tableau est rangé dans le sens inverse il faut à chaque fois faire nt comparaisons. On voit qu'il faudra faire, en moyenne, nt/2 comparaisons pour déterminer la place de l'élément t(nt+1). La complexité en nombre de comparaisons pour trier par insertion n éléments sera donc en O(n²). (Nous verrons en 3.4.4 qu'on peut faire mieux...).

3.4.3. Insérer

L'algorithme est tout aussi simple : il suffit de reculer d'une position tous les éléments du sous-tableau t[place..nt]

x  t (nt+1)
k  nt+1
répéter
    tant que k > place
        t(k)  t(k-1)
        k  k-1
    fin_répéter

Compléxité : "au mieux", si le tableau d'origine est déjà ordonné, le nombre de déplacements peut être nul ; par contre, si le tableau est rangé dans l'ordre inverse il faut faire nt déplacements. On voit qu'il faudra faire, en moyenne, nt/2 déplacements pour insérer l'élément t(nt+1). La complexité en nombre de déplacements pour insérer n éléments sera donc en O(n²).

3.4.4. Déterminer la place où insérer par recherche dichotomique

Pour accélérer la recherche on tient compte du fait que les éléments t(1), t(2) ... t(nt) sont déjà triés (ordonnés) et qu'ils sont stockés dans un tableau, c.-à-d. qu'on peut accéder directement à un élément, quel qu'il soit, du moment qu'on connait son indice.

Etape 1, principe de base :

Rappelons qu'on veut déterminer la place de la valeur "x" dans le tableau.

On suppose avoir déjà obtenu deux indices g et d vérifiant g < d et (1 g < d nt ) délimitant un sous-tableau t[g..d] qui satisfait la relation t(g) x < t(d).

On veut réduire la largeur de l'intervalle [g..d] tout en conservant la relation t(g) x < t(d), pour cela on détermine la position de x par rapport à l'élément médian t(m), ce qui suppose que le "milieu" a un sens, c.-à-d. que m d et m g (ce qui entraîne nécessairement la condition d > g+1) ;

m  (d + g) / 2         /* on suppose t(g)  x < t(d) */
si t(m)  x alors           /* et m  g et m  d */
    g  m
sinon
    d  m
fin_si

Etape 2, itération :

/* on suppose t(g)  x < t(d) */
répéter
    tant_que d > g+1             /* on suppose t(g)  x < t(d) */
        m  (d + g) / 2
        si t(m)  x alors
            g  m
        sinon
            d  m
        fin_si
fin_répéter           /* on sort de t(g)  x < t(d) et d  g+1 */
on remarque que la condition sur d est la même que la condition requise pour place en 3.4.2

Etape 3, initialise :

Il faut donner les valeurs initiales de g et d pour cela :

• méthode naïve : g 1 ; d nt mais avant d'itérer, il faut vérifier la validité de t(1) x < t(nt) ;
• méthode beaucoup moins naïve : On suppose que le tableau t [1..nt] est encadré par 2 éléments virtuels⁷ : t(0) de valeur - et de t(nt+1) de valeur +

  7. Tout le principe de la méthode repose sur cette hypothèse, accompagnée, bien sûr, de la certitude qu'on ne va jamais chercher à examiner le contenu de ces éléments virtuels.

  fermer cette précision

Il va falloir démontrer que la procédure est correcte et, en particulier puisque le seul élément examiné est t(m), il faut vérifier que l'itération maintient toujours m dans [1..nt]. Nous supposerons provisoirement que le tableau n'est pas vide (c.-à-d. nt 1) :

• la condition de répétition est d > g+1 (ce qui équivaut à d g+2)
• l'affectation m (g+d)/2 entraîne m (g + g+2)/2 = g+1
• l'affectation g 0 entraîne m 1, chaque affectation ultérieure donnera à m une suite de valeurs non décroissantes,

De même :

• la condition de répétition est d > g+1 équivaut à d-2 g
• l'affectation m (g+d)/2 entraîne m (d-2 + d)/2 = d-1
• l'affectation d nt+1 entraîne m nt, etc

On aura donc toujours 0 g < m < d nt+1 donc 0 m nt+1 ; d'autre part, les affectations g m et d m entraînent, à chaque étape, le raccourcissement ("division par 2") de [g..d], donc le processus converge.

Remarques :

• si nt = 1 (faux "cas exceptionnel") alors d-g=2, la boucle est exécutée une fois,
• si nt = 0 (vrai cas exceptionnel : la tableau de départ est vide) alors d-g=1, la boucle n'est pas exécutée,
• le choix est inégalités est crucial, par exemple : coder "tant_que d g+1" peut conduire à une répétition éternelle (car peut engendrer m = g et si t(m) < x alors g et d ne changent plus...)
• enfin, il sera instructif de regarder le comportement quand x < t(1) et quand x > t(n).

3.5. Tri-Fusion

A l'origine, c'est un tri "externe" (de données trop nombreuses pour tenir en mémoire et qui étaient stockées sur bandes magnétiques).

Le principe est simple : si on dispose de 2 tableaux déjà triés, la "fusion ordonnée" de ces tableaux produit un tableau ordonné.

On considère un tableau t contenant n éléments. On suppose que ce tableau est constitué d'une succession de sous-tableaux, déjà triés, comportant chacun Lt éléments (sauf, sans doute, le dernier), ces sous-tableaux commencent avec les éléments d'incide 1, Lt+1, 2Lt+1, 3Lt+1, etc. Les fusions de ces sous-tableaux, deux à deux, produisent des sous-tableaux triés comportant 2Lt éléments, que l'on range dans un tableau récepteur w. On débute avec des sous-tableaux dont on est sûr qu'ils sont déjà triés (sous-tableaux de longueur Lt=1).

Dans une analyse descendante, on va écrire la procédure TriFusion en faisant appel à une procédure TriFusLT qui fusionne les sous-tableaux (du tableau t), chacun de Lt éléments déjà ordonnés, et produit un tableau w constitué d'une succession de sous-tableaux, chacun de 2 Lt éléments, ordonnés. Cette procédure TriFusLT fait appel à la procédure Fusion qui réalise la fusion de deux sous-tableaux, déjà ordonnés, en un seul.

Voici les spécifications préliminaires de ces procédures (il faut noter que l'écriture effective des en-têtes des procédures sera très différente selon le langage de programmation : FORTRAN et C permettent de passer des sous-tableaux comme s'il s'agissait de tableaux entiers, PASCAL ne le permet pas ; la liste d'arguments est, ici, assez semblable à celle qu'on écrirait en Pascal) :

procédure TriFusion (   t :        tableau de ty_el_tri [1..n],                                 Entrée/Sortie;
                        n :        nombre d'éléments,                                           Entrée )
                                
procédure TriFusLT (    ti :       tableau de ty_el_tri [1..n],                                 Entrée;
                        n :        nombre d'éléments,                                           Entrée;
                        Lt :       Longueur des sous-tableaux ordonnés,                         Entrée/Sortie;
                                    en entrée, le dernier s-t pourra être le plus court,
                                    en sortie, Lt  2 * Lt
                        tf :       tableau de ty_el_tri [1..n],                                 Sortie )
                        
procédure Fusion (      tA :               s-tableau de ty_el_tri [kAdep..kAfin],               Entrée;
                        kAdep, kAfin :     indices délimitant un s-t de tA trié,                Entrée;
                        tB :               s-tableau de ty_el_tri [kBdep..kBfin],               Entrée;
                        kBdep, kBfin :     indices délimitant un s-t de tB trié,                Entrée;
                        tR :               tableau de ty_el_tri [1..n],                         Entrée;
                        kR :               indice après lequel on range la fusion,              Entrée;
                                           indice du dernier élément rangé,                     Sortie )

3.5.1. Ecriture de TriFusion

Le cœur en est l'appel de TriFusLT (t, n, Lt, w) qui à chaque appel permet de doubler la longueur Lt des sous-tableaux ordonnés. Il suffit de réitérer jusqu'à avoir traité la totalité du tableau, on peut penser qu'entre chaque passe il faut recopier w dans t mais ce n'est pas nécessaire : TriFusLT peut s'en charger.

répéter
    TriFusLT (t, n, Lt, w)     /* 1ère passe : Lt  2*Lt, t  w */
    TriFusLT (w, n, Lt, t)       /* 2ème passe : Lt  2*Lt, w  t */
        en outre, assure la recopie
    jusqu'à Lt  n
        /* la fusion de 2 s-t de longueur  n/2 produit un tableau complètement trié */
fin_répéter

Et voici la procédure complète⁸ :

procédure TriFusion (       t :     tableau de "valeurs" [1..n],        Entrée/Sortie;
                        n :     nombre d'éléments,        Entrée;
                        w :     tableau de "valeurs" [1..n],        tableau de travail )
    variable numérique Lt
    Lt  1
    répéter
        TriFusLT (t, n, Lt, w)      /* 1ère passe : Lt  Lt*2, t  w */
        TriFusLT (w, n, Lt, t)      /* 2ème passe : Lt  Lt*2, w  t */
        jusqu'à Lt  n
            /* la fusion de 2 s-t de longueur  n/2 produit un tableau complètement trié */
    fin_répéter
fin_procédure TriFusion

3.5.2. Ecriture de TriFusLT

Le noyau est l'appel à Fusion (ti, kAdep, kAfin, ti, kBdep, kBfin, tf, kR) :

• à un instant donné on a : kAdep = ?? /* kAdep pointe dans le tableau t */
• on calcule :

  kAfin  kAdep + Lt - 1
  kBdep  kAdep + Lt
  kBfin  kBdep + Lt - 1

• et on appelle Fusion ;
• au passage suivant on fait : kAdeb kBfin + 1
• un problème apparaît quand on arrive à des valeurs de k qui rattrapent n, il suffit de convenir que Fusion devra se débrouiller, même quand un des tableaux est vide (c.-à-d. k_fin k_dep) ; de toutes façons, il convient de fournir à Fusion les valeurs exactes de kAfin et kBfin :

  kAfin  minimum (kAdep + Lt - 1, n)
  kBfin  minimum (kBdep + Lt - 1, n)

Et voici la procédure TriFusLT :

procédure TriFusLT (        ti :       tableau de "valeurs_à_trier" [1..n],             Entrée;
                        n :        nombre d'éléments,                Entrée;
                        Lt :       longueur des sous-tableaux ordonnés,     Entrée/Sortie;
                        tf :       tableau de "valeurs_à_trier" [1..n],     Sortie;
    variable numérique kAdep, kAfin, kBdep, kBfin, kR
    kAdep  1
    kR  0 /* indice du dernier élément rangé dans tf */
    répéter
        tant_que kAdep  n
        kAfin  minimum (kAdep + Lt - 1, n)
        kBdep  kAdep + Lt
        kBfin  minimum (kBdep + Lt - 1, n)
        Fusion (ti, kAdep, kAfin, ti, kBdep, kBfin, tf, kR)
        kAdep  kBfin + 1
    fin_répéter
    Lt  2 * Lt      mise à jour de la longueur des sous-tableaux ordonnés
fin_procédure TriFusLT

3.5.3. Ecriture de Fusion

On commence par écrire ce qu'il faut faire quand il y a des éléments à interclasser dans les deux tableaux. Le cœur est ⁹ :

si ta(kA)  tB(kB)         /* kA et kB pointent vers les prochains éléments à interclasser */
    kR  kR + 1       /* kR pointe vers le dernier élément rangé dans tR */
    tR(kR)  ta(kA)
    kA  kA + 1
sinon
    kR  kR + 1       /* kR pointe vers le dernier élément rangé dans tR */
    tR(kR)  tb(kB)
    kB  kB + 1
fin_si

L'itération est simple :

kA   kAdep
kB   kBdep
répéter
    tant_que kA  kAfin        /* kA et kB pointent vers les prochains éléments à interclasser */
    tant_que kB  kBfin
        incrémenter (kR)      /* kR pointe vers le dernier élément rangé dans tR */
        si ta(kA)  tB(kB) alors
            tR(kR)  ta(kA)
            incrémenter (kA)
        sinon
            tR(kR)  tB(kB)
            incrémenter (kB)
        fin_si
fin_répéter

Après la fin d'éxécution de cette boucle, il faut traiter les "restes", c.-à-d. celui des tableaux tA et tB qui n'a pas été complètement consommé pendant la fusion :

répéter
    tant_que kA  kAfin
        kR  kR + 1
        tR(kR)  ta(kA)
        kA  kA + 1
fin_répéter
répéter       une seule de ces 2 boucles sera exécutée
    tant_que kB  kBfin
        kR  kR + 1
        tR(kR)  tB(kB)
        kB  kB + 1
fin_répéter

N.B. Ainsi écrit, Fusion est "robuste" et résiste aux cas particuliers de tableaux vides ; mais la boucle centrale teste à chaque itération kA et kB, or un seul test suffit car à chaque fois un seul de kA ou kB a changé, aussi on peut améliorer

kA  kAdep
kB  kBdep
si kA  kAfin et kB  kBfin alors
    répéter       /* kA et kB pointent vers les prochains éléments à interclasser */
        incrémenter (kR)     /* kR pointe vers le dernier élément rangé dans tR */
        si tA(kA)  tB(kB) alors    tR(kR)  ta(kA);     incrémenter k(A)
            si kA > kAfin alors cesser de répéter
        sinon
            si kB > kBfin alors cesser de répéter
        fin_si
    fin_répéter
fin_si

Il faut remarquer que Fusion présenter un nombre excessif d'arguments (cf. syntaxe Pascal) ; dans d'autres langages, en particulier en Fortran 90, le nombre d'arguments peut être sensiblement réduit (voir l'exemple plus bas).

3.5.4. Complexité de TriFusion

A chaque appel de TriFusLT il y a n comparaisons et n déplacements, il y a log₂(n) appels à TriFusLT. Donc la complexité en tests et en déplacements vaut Θ(n log(n)) ; revers de la médaille : TriFusion nécessite un tableau de travail de n éléments.

3.5.5. Exemple : en-têtes en Fortran90 (communication automatique des tailles des tableaux)

MODULE Mo_Tri_Fus
    IMPLICIT NONE
    PRIVATE
    PUBLIC :: fusion, tri_Fusion
    
CONTAINS

    SUBROUTINE fusion (tA, tB, tR, nR)
        ! réalise la "fusion ordonnée" de ta et tb, place le resultat dans tr,
        ! gere les cas ta et/ou tb vides
        INTEGER, DIMENSION (1:), INTENT(IN) :: tA, tB ! ordonnés non_decroissants
        INTEGER, DIMENSION (1:), INTENT(OUT) :: tR
        INTEGER, INTENT(OUT) :: nR ! nb elements ranges dans tR
        ! ...... (le reste sans changement par rapport a l'algorithme)
        nA = SIZE (ARRAY= tA)    récupère le nombre effectif (  0) d'éléments du tableau passé en argument ...
        nA = SIZE (ARRAY= tA)    voir CALL fusion ci-dessous
        ! ...... (le reste sans changement par rapport a l'algorithme)
        RETURN
    END SUBROUTINE fusion
    
    SUBROUTINE trifu_StLt (t_org, Lst, t_res)
        INTEGER, DIMENSION (1:), INTENT(IN) :: t_org ! ordonnés non_decroissants
        INTEGER, INTENT(INOUT) :: Lst ! ... par paquets de longueur "Lst"
        INTEGER, DIMENSION (1:), INTENT(OUT) :: t_res ! par paquets de longueur "2 * Lst"
        INTEGER :: n ! nb elements dans t_org
        INTEGER :: kA, kB ! indices debuts st a interclasser
        INTEGER :: nA, nB ! nb elements st a interclasser
        INTEGER :: nn
        n = SIZE (ARRAY= t_org)
        ! ...... (le reste sans changement par rapport a l'algorithme) SAUF :
            CALL fusion (t_org(kA:kA+nA-1), t_org(kB:kB+nB-1), t_res(kA:))
        RETURN
    END SUBROUTINE tridu_StLt
    
    SUBROUTINE tri_Fusion (t)
        INTEGER, DIMENSION (1:), INTENT(INOUT) :: t ! tableau a trier (Entrée), trié (Sortie)
        INTEGER, DIMENSION (1:SIZE (ARRAY= t)) :: w     allocation automatique du tableau
        INTEGER :: n ! nb elements dans t
        INTEGER :: Lst
        n = SIZE (ARRAY= t_org)
        ! ...... (le reste sans changement par rapport a l'algorithme)
        RETURN
    END SUBROUTINE tri_Fusion

END MODULE Mo_Tri_Fus

3.6. Tri "indexé"

Lorsque les clés sont de grande taille ou lorsqu'il y a d'autres informations associées à chaque élément du tableau, on évite de déplacer les éléments ; pour cela on crée un tableau auxiliaire Index qui contiendra l'indice de l'élément considéré ; au lieu d'examiner t(k) on examine t(Index(k)) ; par exemple la condition t(place-1) t(n+1) < t(place) devient : t(Index(place-1)) t(Index(n+1) < t(Index(place))

3.7. Conclusion sur les algorithmes présentés

Les algorithmes de tri par sélection et par insertion sont très simples à programmer. Du fait de leur complexité en n², ils ne peuvent en général être utiles quand le nombre n de données à trier est très faible (quelques dizaines). L'algorithme de tri-fusion est à peine plus compliqué ; il est plus efficace, complexité en n log(n), mais il nécessite un tableau de travail de même taille que le tableau à trier. Nous verrons plus loin des algorithmes très efficaces mais dont la programmation est moins évidente!