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?).
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,
durées de traitement : 2n², 100n log(n), 200 n et 500 log(n) (à 106 opérations par seconde)
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
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) f(n)
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) 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, ω.
"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)
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
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 :
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.
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
à chaque étape, on recherche le plus petit élément (signalé par ) 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.
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) t(2)
...
t(place-1)
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.
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 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).
variables entières : k /* indice pour l'exploration du sous-tableau t[place..n] */ kmin /* indice pointant vers l'élément de valeur minimale */ kminplace 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 */ kminplace 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é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.
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
Il faut dénombrer les opérations élémentaires (à noter que toutes les comparaisons font intervenir un calcul d'adresse dans un 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.
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 :
6. Ici encore, le choix des inégalités < ou est crucial pour la stabilité du tri.
Tri par insertion
à chaque étape, on recherche la position (signalée par ) 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.
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 :
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 :
xt (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...).
L'algorithme est tout aussi simple : il suffit de reculer d'une position tous les éléments du sous-tableau t[place..nt]
xt (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²).
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 :
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.
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) :
De même :
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 :
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
à 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, Lt2 * 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 )
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 : Lt2*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è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.
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 Lt1 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
Le noyau est l'appel à Fusion (ti, kAdep, kAfin, ti, kBdep, kBfin, tf, kR) :
kAfinkAdep + Lt - 1 kBdep
kAdep + Lt kBfin
kBdep + Lt - 1
kAfinminimum (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 kAdep1 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
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) tB(kB) conditionne la stabilité du tri (suggestion :
démontrez cette stabilité).
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 :
kAkAdep 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 kAkAfin 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
kAkAdep 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).
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.
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
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))
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!