Algorithmiq

ue avancée
Chapitre 03: Algorithmes de Tri
 Algorithmes de tri

● Le tri est l’opération qui consiste à présenter une suite

d’éléments dans un ordre précis.
● On s’intéresse au problème de tri car il est souvent requis dans
l’écriture d’autres algorithmes.
● Il devient alors important de développer des algorithmes
efficaces pour le tri surtout lorsque le nombre d’objets à trier est
très grand.
● Les objets à trier peuvent être de plusieurs types. Par souci de
simplicité, dans ce qui suit, nous considérons des nombres réels
et un ordre croissant ou décroissant.
 Plan du chapitre III

01 02 03
Tri par Tri par
Introduction
Sélection Insertion

04
Tri par
05 06
Tri par Fusion Tri Rapide
Propagation

07 08 09
Tri par ABR Tri par TAS Conclusion
INTRODUCTION

Étant donné un tableau d’entiers T (n: sa taille),

l’algorithme du trie permet d’organiser les
éléments du tableau selon un ordre déterminé
(croissant par exemple).
Plusieurs algorithmes de tri existent: tri par
sélection, par insertion, par bulle, par fusion,
rapide, par ABR et par TAS.
L’objectif de ce cours est de concevoir ces
algorithmes de tri de manière récursive, ensuite, de
calculer leur complexité.
 Trier les données
 Organiser une collection d'objets selon une relation d’ordre déterminée.
Exemple:
 Ordre croissant, décroissant des valeurs numériques,
 Ordre croissant des mots, …
 Pourquoi trier?
 Faciliter la recherche (recherche dichotomique)
 Faciliter la gestion en générale
Exemple
 Trier en ordre croisant:
2, 56, 4, -7, 0, 78, -45, 10
 Une solution intuitive:
 Prendre le plus petit
 Prendre le plus petit suivant
 …
-45, -7, 0, 2, 4, 10, 56, 78
 0
1
TRI PAR
SÉLECTION
 TRI PAR SÉLECTION
Principe:
Le principe est de rechercher la plus petite valeur et la placer au début du
tableau, puis la plus petite valeur dans les valeurs restantes et la placer à la
deuxième position et ainsi de suite...
 TRI PAR SÉLECTION
ALGORITHME RÉCURSIF

Tri_Selection (T: tableau, debut, fin : entier)

Debut
Si (debut < fin) alors
min  rechercher_min(T, debut, fin)
Permuter (T, debut, min)
Tri_Selection (T, debut + 1, fin)
FSI
Fin

 T(n) = O(n²)
 TRI PAR SÉLECTION
FONCTION « RECHERCHER_MIN »

Rechercher_min (T: tableau, debut, fin : entier):

entier
Debut
min  debut
Pour i  debut +1 à fin faire
Si (T[i] < T[min]) alors min  i;
Rechercher_min  min;
Fin
 TRI PAR SÉLECTION
COMPLEXITÉ DE LA FONCTION « RECHERCHER_MIN »

Rechercher_min (T: tableau, debut, fin : entier):

entier
Debut
min  debut C1
Pour i  debut +1 à fin faire Nombre d’itération =
Si (T[i] < T[min]) alors min  i; Fin – debut = n-1

Rechercher_min  min; C3
Fin

Tmin (n) = C1 + C2 (n-1) + C3 = C’ n + C’’ 1) + C3 = C’ n + C’’ O(Tmin) = O (n)

 TRI PAR SÉLECTION
COMPLEXITÉ

Tri_Selection (T: tableau, debut, fin : entier)

Debut T (n) tq n = fin – debut + 1
Si (debut < fin) alors
min  rechercher_min(T, debut, fin) Tmin (n)
Permuter (T, debut, min) C3
Tri_Selection (T, debut + 1, fin) T (n - 1)
FSI
Fin

T (n) = T(n-1) + Tmin (n) + C O(T) = O (n² )

0
2
Tri par
insertio
n
 Tri par insertion
Principe:
• Le principe est d’ordonner les deux premiers éléments et d’insérer le 3e élément de manière à ce
que les 3 premiers éléments soient triés, ensuite d’insérer le 4e élément à sa place et ainsi de suite
…
• A la fin de la ieme itération, les i premiers éléments de T sont triés et rangés au début du tableau T.
 Tri par insertion
Algorithme :
Procédure Tri_Insertion (var tab : tableau entier [N])
i, k, tmp : entier;
Pour i de 2 à N faire
tmp  tab[i];
k  i;
Tant que k > 1 ET tab[k - 1] > tmp faire
tab[k]  tab[k - 1];
k  k - 1;
Fin Tant que
tab[k]  tmp;
Fin pour
Fin  T(n) = O(n²)
 Tri par insertion

Calcul de la complexité:
• Au meilleur des cas : le cas le plus favorable pour cet algorithme
est quand le tableau est déjà trié (de taille n)  O(n).
• Au pire des cas : Le cas le plus défavorable pour cet algorithme
est quand le tableau est inversement trié  on fera une itération
pour le 1er élément, deux itérations pour le 2ème et ainsi de suite
pour les autres éléments.
Soit 1+2+3+4+…+(n-1) = n(n+1)/2 -n  sa complexité O(n2)
 0
Tri3
par
propagatio
n (à
bulles)
 Tri par propagation (à bulles)
Principe:
• L'algorithme de tri par propagation (ou à bulles) consiste à faire remonter
progressivement les plus grands éléments d'un tableau.
• Son principe est d’inverser deux éléments successifs s'ils ne sont pas classés dans
le bon ordre et de recommencer jusqu'à ce qu’on ne peut plus permuter.
 Tri par propagation (à bulles)
Algorithme :

Procédure Tri_Bulle (tab : tableau entier [N])

i, k ,tmp : entier ;
Pour i de N à 2 faire
Pour k de 1 à i-1 faire
Si (tab[k] > tab[k+1]) alors
Permuter (T[k], T[k+1]);
Fin si
Fin pour
Fin pour  T(n) = O(n²)
Fin
0
4 Tri par
fusion
 Tri par fusion
Principe:
• Le principe est de trier deux tableaux de taille N/2 et ensuite de les
fusionner de sorte que le tableau final soit trié.
 Tri par fusion
Paradigme diviser pour régner :

• DIVISER: Diviser le tableau en deux tableaux: T[debut..fin]

= T1[debut..milieu] + T2[milieu+1..fin]

• REGNER: trier (par fusion) les deux tableaux

• COMBINER: combiner les 2 tableaux de telle manière que le

tableau T soit trie
 Tri par fusion
Algorithme :

Tri_Fusion (T: tableau, debut, fin : entier)

Debut
Si (debut<fin) alors
milieu  (debut + fin) /2
Tri_Fusion(T, debut, milieu);
Tri_fusion (T, milieu + 1, fin);
Fusionner (T, debut, milieu, fin);
FSI
Fin
 Tri par fusion
Paradigme diviser pour régner
Algorithme :

Procédure fusionner(VAR T: tableau, debut, milieu, fin: entier)

Debut
Tmp: tableau temporaire du taille fin-debut+1
i  debut; gauche  debut; droite  milieu + 1;
Tant que (i <= fin) faire
Si ((gauche <= milieu et T[gauche] <= T[droite]) ou droite > fin) alors
Tmp[i]  T[gauche]; gauche++;
Sinon
Tmp[i]  T[droite]; droite++;
fin_si;
i++;
fin_tq;
Pour i  debut à fin faire T[i]  tmp[i] // recopier le tableau
Fin
 Tri par fusion
Calcul de la complexité: la procédure « fusionner » :
Procédure fusionner(VAR T: tableau, debut, milieu, fin: entier)
Debut Tfusionner (n) avec n= fin – debut +1
Tmp: tableau temporaire du taille fin-debut+1
i  debut; gauche  debut; droite  milieu + 1;
Tant que (i <= fin) faire n fois
Si ((gauche <= milieu et T[gauche] <= T[droite]) ou droite > fin) alors
Tmp[i]  T[gauche]; gauche++;
Sinon
Tmp[i]  T[droite]; droite++;
fin_si;
i++;
fin_tq;
Pour i  debut à fin faire T[i]  tmp[i] // recopier le tableau n fois
Fin T (n) = c * n + c  O (T ) = O(n)
fusionner 1 2 fusionner
 Tri par fusion
Calcul de la complexité:
Tri_Fusion (T: tableau, debut, fin : entier)
Debut
Si (debut<fin) alors
milieu  (debut + fin) /2
Tri_Fusion(T, debut, milieu); T (n/2)
Tri_fusion (T, milieu + 1, fin); T (n/2)
Fusionner (T, debut, milieu, fin) Tfusionner(n)
FSI
Fin

T(n) = 2T(n/2) + Tfusionner(n) O(T) = O(n log2 n)

0
5
Tri
rapide
 Tri rapide
Principe:
• Le principe est de choisir une valeur dans le tableau appelée pivot (par
exemple la première valeur du tableau) et de déplacer avant elle toutes celles
qui lui sont inférieures et après elle toutes celles qui lui sont supérieures.
• Réitérer le procédé avec la tranche de tableau inférieure et la tranche de
tableau supérieure à ce pivot.
 Tri rapide
Paradigme diviser pour régner

DIVISER: Diviser le tableau en deux tableaux selon le

pivot choisi : T1[debut..pivot-1] et T2[pivot+1..fin].

REGNER: trier (par trie rapide) les deux tableaux.

COMBINER: combiner les 2 tableaux :

T [debut..fin] = T1[debut..pivot] + T2[pivot+1..fin] est
trié.
 Tri rapide
Algorithme récursif :

Tri_Rapide (T: tableau, debut, fin : entier)

Debut
SI (debut < fin) alors
Pivot  partitionner(T, debut, fin, pivot)
Tri_Rapide(T, debut, pivot-1)
Tri_Rapide(T, pivot+1, fin)
FSI
Fin
 Tri rapide
Fonction « partitionner » :
Partitionner (T: tableau, debut, fin, pivot: entier): entier
Debut
permuter (T[pivot], T[fin])
j  debut
Pour i  debut à fin -1 faire
SI T[i] <= T[fin] alors
Permuter (T[i], T[j])
jj+1
FSI
FP
Permuter (T[fin] , T[j])
Partitionner  j
Fin
 Tri rapide
Calcul de la complexité: la fonction « partitionner » :
Partitionner (T: tableau, debut, fin, pivot: entier): entier
Debut Tpartitionner (n) avec n= fin – debut +1
permuter (T[pivot], T[fin])
j  debut
Pour i  debut à fin -1 faire Pire de cas: n-1 fois
SI T[i] <= T[fin] alors
Permuter (T[i], T[j])
jj+1
FSI
FP
Permuter (T[fin] , T[j])
Partitionner  j
Fin Tpartitionner (n) = c1 * n + c2  O(T) = O(n)
 Tri rapide
Calcul de la complexité:

Tri_Rapide (T: tableau, debut, fin : entier) T(n) avec n= fin – debut +1
Debut
SI debut < fin alors
Pivot  partitionner(T, debut, fin , pivot) Tpartitionner (n)
Tri_Rapide(T, debut, pivot-1) T(pivot - debut)
Tri_Rapide(T, pivot+1, fin) T(fin - pivot)
FSI
Fin

T(n) = T(pivot - debut) + T(fin - pivot) + Tpartitionner (n)

 Tri rapide
Choix du pivot et complexité :
T(n) = T(pivot-debut+1) + T(fin-pivot) + Tpartitionner (n)

• Cas 1: Pivot aléatoire: la complexité moyenne du tri rapide en

sélectionnant le pivot de cette façon est O(n log2 n).
• Le pire cas intervient quand le partitionnement produit une
région à n-1 éléments et une région à un élément:
T(n) = T(n-1) + T(1) + Tpartitionner(n) = T(n-1) + f(n)
 O(T) = O(n2)
• Cas 2: Pivot Arbitraire: (premier élément, dernier élément ou
élément en milieu ). Même chose que le cas 1.
 Tri rapide

Choix du pivot et complexité :

T(n) = T(pivot-debut+1) + T(fin-pivot) + Tpartitionner (n)

• Cas 3: Pivot optimal: comme la valeur médiane qui permet de

couper le tableau en deux parties égales de taille n/2 :
T(n) = 2T(n/2) + Tpartitionner(n)
 O(T) = O(n log2n)
0
6 par
Tri
ABR
 Tri par ABR
Définition : Un Arbre Binaire de Recherche (ABR) est un arbre binaire, dans
lequel chaque noeud contient un entier en respectant les propriétés suivantes :
– Supérieur (ou égal) aux entiers de son sous-arbre gauche.
– Inférieur strictement aux entiers de son sous-arbre droit.

2
0

1 3
5 5
2 4
1
5 0
0 1
5 1 9 3
3 8
1
3 7 6
 Tri par ABR
Principe :
1. Insérer tous les éléments du tableau dans un ABR

2
0

1 3
5 5
2 4
1
5 0
0 1
5 1 9 3
3 8
1
3 7 6
 Tri par ABR
Principe :
2. Parcourir l’ABR en ordre infixé : SAG, noeud, SAD
2
0

1 3
5 5
2 4
1
5 0
0 1
5 1 9 3
3 8
1
3 7 6
12
 Tri par ABR
Algorithme itératif : Soit ABR un arbre binaire de recherche
Tri_ABR_IT (T: Tableau, n: entier)
Type
noeud = enregistrement
valeur : entier;
FG : ^noeud;
FD : ^noeud;
end;
Var
ABR : ^noeud // Construire ABR
Debut
ABR  Nil
Pour i  1 à n faire
ABR  Insérer (ABR, T[i]).
Parcours_Infixe (ABR, T, 1); //Parcours Infixe
Fin
 Tri par ABR
Fonction « insérer » :
Insérer (AR: nœud, x: entier): nœud
Debut
SI (AR=Nil) alors // L’arbre est vide
allouer(AR); // Créer la racine (le premier nœud)
AR.valeur  x;
SINON SI (x ≤ AR.valeur) alors
AR.FG  Insérer(AR.FG, x) // Insérer à gauche
SINON
AR.FD  Insérer(AR.FD, x) // Insérer à droite
FSI
Insérer  AR
Fin
 Tri par ABR
Terminologie : Si h est la hauteur d’un arbre binaire de
recherche, et n le nombre des nœuds (ou la taille du tableau).

h=0 20

h=1 1 3
5 5 h=
10 1 25 4 4
h=2
9 0 n=
h=3 5 1 16 38 14
3
h=4 3 7
12
 Tri par ABR
Complexité de la fonction « insérer » :
Insérer (AR: nœud, x: entier): nœud Tinsérer(h) tq h est la hauteur de l’arbre
Debut
SI (AR=Nil) alors // L’arbre est vide
allouer(AR); // Créer la racine (le premier nœud)
AR.valeur  x;
SINON SI (x ≤ AR.valeur) alors
AR.FG  Insérer(AR.FG, x) // Insérer à gauche Tinsérer(h-1)
SINON
AR.FD  Insérer(AR.FD, x) // Insérer à droite Tinsérer(h-1)
FSI
Insérer  AR
Fin
Pire des cas : Tinsérer(h) = Tinsérer (h-1) + c O(Tinsérer ) = O(h)
 Tri par ABR
O(Tinsérer) = O(h)
Complexité de la fonction « insérer » :
• Pire des cas : un tableau trié par ordre inverse (ou déjà trié)
⇒ Arbre mal équilibré ⇒ h = n-1 ⇒ O(Tinsérer) = O(n-1) = O(n)

h=0 25

h=
h=1 18 4
n=5
h=2 15

h=3 5

h=4 2
 Tri par ABR
Parcours infixé : le paramètre «indice» initialisé à 1
Parcours_Infixe (AR: nœud, T: Tableau, indice: entier)
Debut
Si ( AR ≠ Nil) alors //Arbre n’est pas vide
Parcours_Infixe(AR.FG, T, indice)
T[indice]  AR.valeur //Écrire la valeur dans le tableau
Indice  indice + 1;
Parcours_Infixe(AR.FD, T, indice)
FSI
Fin
 Tri par ABR
Complexité du parcours infixé :
Parcours_Infixe (AR: nœud, T: Tableau, indice: entier)
Debut Tinfixe (n) tq n le nombre des nœuds
Si ( AR ≠ Nil) alors //Arbre n’est pas vide
Parcours_Infixe(AR.FG, T, indice)) Tinfixe (k)
T[indice]  AR.valeur //Écrire la valeur dans le tableau
Indice  indice + 1;
Parcours_Infixe(AR.FD, T, indice) Tinfixe (n-k-1)
FSI
Fin

Tinfixe (n) = Tinfixe (k) + Tinfixe (n-k-1) + c

 Tri par ABR
Complexité du parcours infixé :
Tinfixe (n) = Tinfixe (k) + Tinfixe (n-k-1) + c
• Évidemment, le parcours infixé passe par tous les nœuds de
l’arbre, ainsi : O(Tinfixe) = O(n)
Démonstration par récurrence :
– Cas évident n = 0, T(0) = 0 ⇒ O(T) = O(0) = O(n) vérifiée
– Hypothèse de récurrence pour k<n , on a O(T) = O(k)
⇒ T(k) = a k + b
– Cas général:
Tinfixe (n) = Tinfixe (k) + Tinfixe (n-k-1) + c
Tinfixe (n) = a k + b + a (n-k-1) + b + c = a n + (2 b – a + c)
Tinfixe (n) = a n + d ⇒ O(Tinfixe) = O(n)
 Tri par ABR
Complexité de l’algorithme itératif :
Tri_ABR_IT (T: Tableau, n: entier) TABR (n)
Type
noeud = enregistrement
valeur : entier;
FG : ^noeud; O(TABR)= n * O(n) + O(n)
FD : ^noeud;
= O(n2) + O(n)
end;
Var = O(n2)
ABR : ^noeud // Construire ABR
Debut
ABR  Nil
Pour i  1 à n faire n fois
ABR  Insérer (ABR, T[i]). Tinsérer (n)
Parcours_Infixe (ABR, T, 1); //Parcours Infixe Tinfixe (n)
Fin
 Tri par ABR
Algorithme récursif :

Tri_ABR(T: Tableau, n: entier, AR: nœud) TABR (n)

Debut
SI (n>0) alors Tinsérer (n)
Insérer (ABR, T[n])
Tri_ABR(T, n-1, ABR) TABR (n-1)
SINON // n=0 l’arbre est construit en totalité
Parcours_Infixe (ABR, T, 1); Tinfixe (n)
FISI
FIN

TABR (n)= TABR (n – 1 ) + Tinsérer (n) ⇒ O (TABR ) = O(n2)

0
7
Tri par TAS
 Tri par TAS

Définition : Un TAS est un arbre binaire qui vérifie les deux

propriétés suivantes :
– Propriété structurelle : arbre binaire complet (ou parfait),
i.e. Tous les niveaux sont totalement remplis sauf le
dernier qui est rempli de la gauche vers la droite.
– Propriété d’ordre :
• TASmin: valeur (père) ≤ valeur (fils)
• TASmax: valeur (père) ≥ valeur (fils)
 Tri par TAS

TASMIN:
 Tri par TAS
TASMAX:
 Tri par TAS
Hauteur d’un TAS :
Théorème : Un TAS de n nœud a une hauteur O(log2n)

Conséquence : Les opérations proportionnelle à h sont on

O(log2n)
 Tri par TAS

Hauteur d’un TAS :

Théorème : Un TAS de n nœud a une hauteur h = log2n
Démonstration : Soit h, la hauteur d’un TAS de n nœud
• Au niveau i≠h, ni=2i
• Donc n = 20 + 21 + 22 + ....+ 2h-1 + c tel que, 0 < c ≤ 2h
n = 2h - 1 + c ≥ 2h ⇒ h ≤ log2n ⇒ O(h) = O(log2n).

Conséquence : Les opérations proportionnelle à h sont on

O(log2n)
 Tri par TAS
Représentation par tableau: un TAS se représente naturellement
par un tableau:
– Les sommets sont numérotés par un parcours en largeur,
de gauche à droite.
– Le sommet «i» est rangé dans la case d’indice i du tableau.

5
6
 Tri par TAS

Représentation par tableau :

• Indice(racine) = 1
• Indice(FG) = 2*Indice(Père)
• Indice(FD) = 2*Indice(Père)+1
• Indice(Père) = [Indice(Fils)/2]
 Tri par TASMIN
Insertion :
• Pour insérer une valeur « v » dans un TASmin
1) Insérer «v» à la fin du dernier niveau de l’arbre (à la fin
du tableau).
2) Tant que la valeur du père de «v» est plus grande que
«v», échanger la valeur du père de v avec «v».
Exemple: insertion de 3
Tri par TASMIN

3
 Tri par TASMIN
Insertion :
Procédure Insérer_TAS (Tas: tableau, n, x: entier)
Début
nn+1
in
Tas[i]  x
Tant que (i/2 > 0 et Tas[i/2] > x) faire
Permuter (Tas[i], Tas[i/2])
i  i/2
Fi_tq
Fin
 Tri par TASMIN
Complexité de la procédure Insérer_TAS :
Procédure Insérer_TAS (Tas: tableau, n, x: entier) TInsérer ??
Début
Pire des cas: le n+1ème élément
nn+1
du tableau est le minimum ⇒ le
in nombre d’itération de la boucle
Tas[i]  x correspond à la hauteur de
Tant que (i/2 > 0 et Tas[i/2] > x) faire l’arbre donc égale à log2(n+1)
Permuter (Tas[i], Tas[i/2])
i  i/2
fi_tq
Fin

Tinsérer (n) = c1 log2(n+1) + c2 ⇒ O(TInsérer) = O(log2(n+1))

 Tri par TASMIN
Extraire le minimum : Le minimum se trouve à la racine.
Pour supprimer la racine:
1) Remplacer la racine par le dernier élément de tableau.
2) Tant que la valeur « v » est supérieure à celle de l’un de ses fils,
échanger la valeur « v » avec celle la plus petit de ses fils.
Exemple :
Tri par TASMIN
Tri par TASMIN
 Tri par TASMIN
Extraire le minimum :
ExtraireMin (Tas: tableau, n : entier )
Début
Tas[1]  Tas[n];
min  1; Sortie  faux;
Tant que (non sortie) faire
i  min; g  2*i; d  2*i + 1;
Si g < n et Tas[g] < Tas[min] alors min  g;
Si d < n et Tas[d] < Tas[min] alors min  d;
Si min ≠ i alors Permuter (Tas[i], Tas[min])
Sinon Sortie  vrai;
fi_tq
Fin
 Tri par TASMIN
Complexité de la procédure Extraire_minimum :
ExtraireMin (Tas: tableau, n : entier ) Textraire ??
Début
Tas[1]  Tas[n];
Pire des cas: le dernier
min  1; Sortie  faux; élément est le maximum
Tant que (non sortie) faire ⇒ le nombre d’itération
i  min; g  2*i; d  2*i + 1; correspond à la hauteur
Si g < n et Tas[g] < Tas[min] alors min  g; de l’arbre donc égale à
Si d < n et Tas[d] < Tas[min] alors min  d; log2n
Si min ≠ i alors Permuter (Tas[i], Tas[min])
Sinon Sortie  vrai;
fi_tq
Fin T (n) = c log n + c ⇒ O(T ) = O(log n)
Extraire 3 2 4 Extraire 2
 Tri par TASMIN
Principe :
1. Transformer le tableau en un TASMIN
2. Extraire n fois le minimum du TAS
 Tri par TASMIN (principe)

1. Transformer le tableau en un TASMIN :

 Tri par TASMIN (principe)
1. Transformer le tableau en un TASMIN :

Le tableau final (le TAS) est comme suite:

 Tri par TASMIN (principe)

2. Extraire n fois le minimum du TAS :

 Tri par TASMIN (principe)

2. Extraire n fois le minimum du TAS :

 Tri par TASMIN (principe)
2. Extraire n fois le minimum du TAS :
 Tri par TASMIN (principe)
2. Extraire n fois le minimum du TAS :
 Tri par TASMIN
Algorithme itératif :
Tri_TASmin (T: Tableau, n: entier)
Début
//Construire le TAS
Pour i  1 à n faire
Insérer_TAS (Tas, i-1, T[i])
// Extraire les minimums
Pour i  0 à n-1 faire
T[i+1]  TAS[1]
ExtraireMin (TAS, n - i)
Fi_pour
Fin
 Tri par TASMIN

Complexité de l’algorithme itératif :

Tri_TASmin (T: Tableau, n: entier) TTAS(n) tq n la taille du tableau
Début
//Construire le TAS
Pour i  1 à n faire
Insérer_TAS (Tas, i-1, T[i]) TInsérer
// Extraire les minimums
Pour i  0 à n-1 faire
T[i+1]  TAS[1]
ExtraireMin (TAS, n - i) Textraire
Fi_pour
Fin
 Tri par TASMIN
Complexité de l’algorithme itératif :
Tri_TASmin (T: Tableau, n: entier) TTAS(n) tq n la taille du tableau
Début
//Construire le TAS
Pour i  1 à n faire
Insérer_TAS (Tas, i-1, T[i]) TInsérer(i-1) = O(log2i)
// Extraire les minimums
Pour i  0 à n-1 faire
T[i+1]  TAS[1]
ExtraireMin (TAS, n - i) Textraire (n-i) = O(log2(n-i))
Fi_pour
Fin
O(TTAS) = O(nlog2n)
 Tri par TASMIN
Algorithme récursif :
i  1; phase  1
Tri_TASmin (T, TAS: Tableau, n, i, phase: entier)
Début
Si Phase = 1 alors //Construire le TAS
Si (i<=n) alors
Insérer_TAS (Tas, i-1, T[i])
Tri_TASmin (T, TAS, i++, n, phase)
Sinon
Tri_TASmin(T, TAS, 0, n, 2) // On passe à la phase 2
Sinon // Phase 2: Extraire les minimums
Si (i<n) alors
T[i+1]  TAS[1]
ExtraireMin (TAS, n-i)
Tri_TASmin (T, TAS, i++, n, phase)
Fsi
Fin
 Tri par TASMIN
Complexité de l’algorithme récursif :
i  1; phase  1
Tri_TASmin (T, TAS: Tableau, n, i, phase: entier) TTAS(m) tq m = n-i+1
Début la taille effective du
Si Phase = 1 alors //Construire le TAS tableau (m ≤ n)
Si (i<=n) alors
O(TInsérer) = O(log2(n-m+1))
Insérer_TAS (Tas, i-1, T[i])
Tri_TASmin (T, TAS, i++, n, phase) TTAS(m-1)
Sinon
Tri_TASmin(T, TAS, 0, n, 2) // On passe à la phase 2
Sinon // Phase 2: Extraire les minimums
Si (i<n) alors
T[i+1]  TAS[1] O(Textraire) = O(log2(m-1))
ExtraireMin (TAS, n-i) TTAS(m-1)
Tri_TASmin (T, TAS, i++, n, phase)
Fsi O(TTAS) = O(nlog2n)
Fin
Conclusion