Kha-tastrophe.net

Le site kha-tastrophique de Kha

> 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).

Croissances comparées des durées d'exécution en fonction du nombre n d'objets traités,

Croissances comparées des durées d'exécution en fonction du nombre n d'objets traités

durées de traitement : 2n², 100n log(n), 200 n et 500 log(n) (à 106 opérations par seconde)

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ée1.

1. Et peuvent varier d'un auteur à l'autre, nous suivons ici les notations de Cormen, Leiserson et River

fermer cette précision

Considérons f et g, deux fonctions de n à valeurs positives. On dira que f croît comme Θ(g) si il existe deux constantes c1 et c2 positives et une valeur n0 telles que pour tout n > n0 on ait c1 g(n) Symbole : inférieur et égal f(n) Symbole : inférieur et égal c2 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 n0 telles que pour tout n > n0 on ait f(n) Symbole : inférieur et égal 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) Symbole : inférieur et égal 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.

carte perforée (taille réelle : 187 x 83 mm)

Carte perforée

La carte est divisée en 80 colonnes de 12 lignes (ces lignes sont numérotées, haut en bas, 12, 11, 0, 1, 2, ...9), chaque colonne peut comporter des perforations qui correspondent au codage d'un caractère (en haut de la carte est imprimée l'interprétation de ces perforations); par exemple les chiffres sont codés à l'aide d'une seule perforation sur la ligne correspondante.

Simulation du tri d'un paquet de cartes perforées à l'aide d'une trieuse de cartes

Simulation du tri d'un paquet de cartes perforées à l'aide d'une trieuse de cartes

La machine empile dans une même case les cartes qui ont la même perforation dans une colonne choisie : à la fin de chaque étape, on regroupe, dans l'ordre, le contenu des case.

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) Symbole : inférieur et égal 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.

Tri par sélection

Schéma illustrant le principe du tri par sélection

à chaque étape, on recherche le plus petit élément (signalé par Symbole : flèche double) du sous-tableau restant à trier, on l'échange avec le premier élément de ce sous-tableau (signalé en caractères gras), puis on trie ce sous-tableau privé de son premier élément ; les éléments déplacés pendant l'étape précédente sont écrits en italique. Quand on commence une étape, le sous-tableau situé au-dessus de la barre est ordonné et les éléments du sous-tableau situé en dessous sont plus grands (ou, au moins, ne sont pas plus petits) que ceux du sous-tableau du haut.

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 tableau2 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) Symbole : inférieur et égal t(2) Symbole : inférieur et égal ... Symbole : inférieur et égal t(place-1) Symbole : inférieur et égal t[place..n].

2. Pour faciliter la lecture, nous désignerons par [n1..n2] l'ensemble des valeurs n1, n1+1, n1+2, ..., n2 et par t[n1..n2] le sous-tableau du tableau t dont les éléments sont t(n1), t(n1+1), t(n1+2), ..., t(n2) ; bien évidemment, t(n) désigne l'élément d'indice n du tableau t.

fermer cette précision

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) Symbole : inférieur et égal t(2) Symbole : inférieur et égal ... Symbole : inférieur et égal t(place-1) Symbole : inférieur et égal t(place) Symbole : inférieur et égal t[place+1..n]

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

3. Rappelons que, lorsqu'on cherche le minimum (ou le maximum) des éléments d'un ensemble, il faut toujours initialiser la variable où est stockée la valeur du minimum provisoire avec la valeur d'un élément de l'ensemble (et pas avec une valeur "bien choisie" comme on le voit trop souvent).

fermer cette précision

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 Symbole : affectation 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 Symbole : inférieur et égal : on choisit, en général, de ne déplacer l'élément
        kmin Symbole : affectation k         que si il est indispensable qu'il soit déplacé pour que la relation t(k) Symbole : inférieur et égal 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 Symbole : affectation place
    répéter pour k variant de place+1 à n
        si t(k) < t(kmin) alors
            kmin Symbole : affectation k
        fin_si
    fin_répéter
    échanger (t(kmin), t(place))
fin_répéter

Etape 3, mise en forme de la procédure4,5 :

4. Ici encore, le type ty_el_tri est un type générique.

5. L'indication indice [1..?] pour nous rappeler que la forme de cette spécification sera très liée au langage de programmation effectivement utilisé. Il sera instructif de comparer les différentes façons d'écrire cet en-tête selon les langages utilisés.

fermer cette précision


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) Symbole : inférieur et égal 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 que6 t(place-1) Symbole : inférieur et égal t(nt+1) < t(place)

    6. Ici encore, le choix des inégalités < ou Symbole : inférieur et égal 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]

Tri par insertion

Schéma illustrant le principe du tri par insertion directe

à chaque étape, on recherche la position (signalée par Symbole : flèche double) où insérer l'élément (écrit en caractères gras) qu'on veut ajouter au sous-tableau déjà trié. On a écrit en italiques les éléments déplacés pendant l'étape précédente.

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) Symbole : inférieur et égal x < t(place)

L'algorithme est immédiat :

x Symbole : affectation t (nt+1)
place Symbole : affectation nt+1
répéter      /* tant que la condition t(place-1) Symbole : inférieur et égal x < t(place) n'est pas vérifiée */
    tant que place > 1      /* et tant qu'on peut */
    jusqu'à t(place-1) Symbole : inférieur et égal 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 Symbole : affectation t (nt+1)
k Symbole : affectation nt+1
répéter
    tant que k > place
        t(k) Symbole : affectation t(k-1)
        k Symbole : affectation 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 Symbole : inférieur et égal g < d Symbole : inférieur et égal nt ) délimitant un sous-tableau t[g..d] qui satisfait la relation t(g) Symbole : inférieur et égal x < t(d).

On veut réduire la largeur de l'intervalle [g..d] tout en conservant la relation t(g) Symbole : inférieur et égal 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 Symbole : différent d et m Symbole : différent g (ce qui entraîne nécessairement la condition d > g+1) ;

m Symbole : affectation (d + g) / 2         /* on suppose t(g) Symbole : inférieur et égal x < t(d) */
si t(m) Symbole : inférieur et égal x alors           /* et m Symbole : différent g et m Symbole : différent d */
    g Symbole : affectation m
sinon
    d Symbole : affectation m
fin_si

Etape 2, itération :

/* on suppose t(g) Symbole : inférieur et égal x < t(d) */
répéter
    tant_que d > g+1             /* on suppose t(g) Symbole : inférieur et égal x < t(d) */
        m Symbole : affectation (d + g) / 2
        si t(m) Symbole : inférieur et égal x alors
            g Symbole : affectation m
        sinon
            d Symbole : affectation m
        fin_si
fin_répéter           /* on sort de t(g) Symbole : inférieur et égal x < t(d) et d Symbole : inférieur et égal 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 Symbole : affectation 1 ; d Symbole : affectation nt mais avant d'itérer, il faut vérifier la validité de t(1) Symbole : inférieur et égal x < t(nt) ;
  • méthode beaucoup moins naïve : On suppose que le tableau t [1..nt] est encadré par 2 éléments virtuels7 : t(0) de valeur -Symbole : infini et de t(nt+1) de valeur +Symbole : infini

    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 Symbole : supérieur et égal 1) :

  • la condition de répétition est d > g+1 (ce qui équivaut à d Symbole : supérieur et égal g+2)
  • l'affectation m Symbole : affectation (g+d)/2 entraîne m Symbole : supérieur et égal (g + g+2)/2 = g+1
  • l'affectation g Symbole : affectation 0 entraîne m Symbole : supérieur et égal 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 Symbole : supérieur et égal g
  • l'affectation m Symbole : affectation (g+d)/2 entraîne m Symbole : inférieur et égal (d-2 + d)/2 = d-1
  • l'affectation d Symbole : affectation nt+1 entraîne m Symbole : inférieur et égal nt, etc

On aura donc toujours 0 Symbole : inférieur et égal g < m < d Symbole : inférieur et égal nt+1 donc 0 Symbole : inférieur et égal m Symbole : inférieur et égal nt+1 ; d'autre part, les affectations g Symbole : affectation m et d Symbole : affectation 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 Symbole : supérieur et égal 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).

Principe du Tri-Fusion

Schéma illustrant le principe du tri Fusion

à chaque étape, on fusionne 2 à 2 des sous-tableaux préalablement ordonnés, produisant des sous-tableaux ordonnés 2 fois plus grands.

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 Symbole : affectation 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 Symbole : affectation 2*Lt, t Symbole : flèche vers la droite w */
    TriFusLT (w, n, Lt, t)       /* 2ème passe : Lt Symbole : affectation 2*Lt, w Symbole : flèche vers la droite t */
        en outre, assure la recopie
    jusqu'à Lt Symbole : supérieur et égal n
        /* la fusion de 2 s-t de longueur Symbole : supérieur et égal n/2 produit un tableau complètement trié */
fin_répéter

Et voici la procédure complète8 :

8. La façon d'allouer le tableau de travail w va dépendre du langage utilisé : obligatoirement statique (et fourni par le programme appelant) en FORTRAN 77, elle peut être dynamique en PASCAL, C ou "automatique" en FORTRAN 90.

fermer cette précision

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 Symbole : affectation 1
    répéter
        TriFusLT (t, n, Lt, w)      /* 1ère passe : Lt Symbole : affectation Lt*2, t Symbole : flèche vers la droite w */
        TriFusLT (w, n, Lt, t)      /* 2ème passe : Lt Symbole : affectation Lt*2, w Symbole : flèche vers la droite t */
        jusqu'à Lt Symbole : supérieur et égal n
            /* la fusion de 2 s-t de longueur Symbole : supérieur et égal 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 Symbole : affectation kAdep + Lt - 1
    kBdep Symbole : affectation kAdep + Lt
    kBfin Symbole : affectation kBdep + Lt - 1
  • et on appelle Fusion ;
  • au passage suivant on fait : kAdeb Symbole : affectation 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 Symbole : inférieur et égal k_dep) ; de toutes façons, il convient de fournir à Fusion les valeurs exactes de kAfin et kBfin :
    kAfin Symbole : affectation minimum (kAdep + Lt - 1, n)
    kBfin Symbole : affectation 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 Symbole : affectation 1
    kR Symbole : affectation 0 /* indice du dernier élément rangé dans tf */
    répéter
        tant_que kAdep Symbole : inférieur et égal n
        kAfin Symbole : affectation minimum (kAdep + Lt - 1, n)
        kBdep Symbole : affectation kAdep + Lt
        kBfin Symbole : affectation minimum (kBdep + Lt - 1, n)
        Fusion (ti, kAdep, kAfin, ti, kBdep, kBfin, tf, kR)
        kAdep Symbole : affectation kBfin + 1
    fin_répéter
    Lt Symbole : affectation 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 9 :

9. Ici encore, le choix de l'inégalité : ta(kA) < tB(kB) ou ta(kA) Symbole : inférieur et égal tB(kB) conditionne la stabilité du tri (suggestion : démontrez cette stabilité).

fermer cette précision

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

L'itération est simple :

kA Symbole : affectation  kAdep
kB Symbole : affectation  kBdep
répéter
    tant_que kA Symbole : inférieur et égal kAfin        /* kA et kB pointent vers les prochains éléments à interclasser */
    tant_que kB Symbole : inférieur et égal kBfin
        incrémenter (kR)      /* kR pointe vers le dernier élément rangé dans tR */
        si ta(kA) Symbole : inférieur et égal tB(kB) alors
            tR(kR) Symbole : affectation ta(kA)
            incrémenter (kA)
        sinon
            tR(kR) Symbole : affectation 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 Symbole : inférieur et égal kAfin
        kR Symbole : affectation kR + 1
        tR(kR) Symbole : affectation ta(kA)
        kA Symbole : affectation kA + 1
fin_répéter
répéter       une seule de ces 2 boucles sera exécutée
    tant_que kB Symbole : inférieur et égal kBfin
        kR Symbole : affectation kR + 1
        tR(kR) Symbole : affectation tB(kB)
        kB Symbole : affectation 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 Symbole : affectation kAdep
kB Symbole : affectation kBdep
si kA Symbole : inférieur et égal kAfin et kB Symbole : inférieur et égal 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) Symbole : inférieur et égal tB(kB) alors    tR(kR) Symbole : affectation 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 log2(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 ( Symbole : supérieur et égal 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) Symbole : inférieur et égal t(n+1) < t(place) devient : t(Index(place-1)) Symbole : inférieur et égal 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 , 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!