Algorithmique & Complexité – Travaux dirigés n°4

Algorithmes de Tri : Algorithmique & Complexité II : Chapitre 1

Tri par sélection

Sur un tableau de n éléments (numérotés de 1 à n), le principe du tri par sélection est le suivant :
rechercher le plus petit élément du tableau, et l'échanger avec l'élément d'indice 1 ; rechercher le
second plus petit élément du tableau, et l'échanger avec l'élément d'indice 2 ; continuer de cette
façon jusqu'à ce que le tableau soit entièrement trié. En pseudo-code, l'algorithme s'écrit ainsi :

Selection-sort(A,n)
Begin
for i = 1 to n – 1 do
min = i
for j = i + 1 to n do
if A[j] < A[min] then min = j
if min ≠ i then swap(A[i], A[min])
End

Dans tous les cas, pour trier n éléments, le tri par sélection effectue n(n-1)/2 comparaisons. Sa
complexité est donc (n²).

Version récursive (appel initial Selection-sort-recursive (A, 1, n)) :

Selection-sort-recursive (A,i,n)
Begin
if i ≤ n-1 then
min = i
for j = i + 1 to n do
if A[j] < A[min] then min = j
if min ≠ i then swap(A[i], A[min])
Selection-sort-recursive (A,i+1,n)
End

En appliquant le théorème de dérécursivation du cours, on pourra vérifier aisément que l’on

retrouve la version itérative de l’algorithme :

Selection-sort-derecursive (A,n)
Begin
i=1
while i ≤ n-1 do
min = i
for j = i + 1 to n do
if A[j] < A[min] then min = j
if min ≠ i then swap(A[i], A[min])
i =i+1
End

 Mohamed Bécha Kaâniche - oct.-10

Exemple d’implémentation en C++ (Bonus):

#include <iostream>
#include <vector>

using namespace std;

/**
* Generic function returning the minimum of table @param A starting
* from the index @param k to the end of the table
*/
template <typename T>
unsigned long min(vector<T> A,unsigned long k){
T minimum = A[k];
unsigned long min_index = k;
for (unsigned long i = k+1 ; i<A.size() ; i++){
if(A[i] < minimum){
minimum = A[i];
min_index = i;
}
}
return min_index;
}

/**
* Generic function swapping two elements indexed by
* @param a and @param b of the table @param A
*/
template <typename T>
void swap(vector<T> &A,unsigned long a,unsigned long b){
T temp;
temp = A[a];
A[a] = A[b];
A[b] = temp;
}

/**
* Selection sort.
*/
template <typename T>
void selection_sort(vector<T> &A){
for(unsigned long i = 0 ; i<A.size() -1 ; i++){
swap(A,i,min(A,i));
}
}

Questions

1. Vérifiez que la complexité de cet algorithme en nombre de comparaisons est en (n²)

2. Vérifiez que la complexité de cet algorithme en nombre d’échanges est en (n)
3. (Bonus) Ecrivez en C++ le code relatif à la version récursive de cet algorithme.

 Mohamed Bécha Kaâniche - oct.-10

Tri par insertion
Dans cet algorithme, on parcourt le tableau à trier du début à la fin. Au moment où on considère le i-
ème élément, les éléments qui le précèdent sont déjà triés. L'objectif d'une étape est d'insérer le i-
ème élément à sa place parmi ceux qui précèdent. Il faut pour cela trouver où l'élément doit être
inséré en le comparant aux autres, puis décaler les éléments afin de pouvoir effectuer l'insertion. En
pratique, ces deux actions sont fréquemment effectuées en une passe, qui consiste à faire «
remonter » l'élément au fur et à mesure jusqu'à rencontrer à un élément plus petit.

Dans la première partie du cours, on a déjà étudié la version itérative de cet algorithme. Sa
complexité au meilleur cas étant en (n), dans la moyenne des cas et au pire cas en (n²).

Version récursive (appel initial Insertion-sort-recursive (A, n)) :

Insertion-sort-recursive (A, n)
Begin
if n > 1 then
Insertion-sort-recursive (A, n - 1);
if A[n] < A[n - 1] then
aux:= A[n];
i := n;
repeat
A[i] := A[i - 1];
i := i - 1;
until (i = 1) or (aux > A[i - 1]);
A[i] := aux;
End

Questions

1. Vérifiez que la complexité de cette version en nombre de comparaisons est en (n²)

2. En appliquant le théorème du cours, dérécursivez cette version et vérifiez qu’elle est équivalente
à la version itérative proposée en cours.
3. (Bonus) Ecrivez en C++ le code relatif aux versions itérative et récursive de cet algorithme.

Tri à bulles
Le tri à bulles ou tri par propagation est un algorithme de tri qui consiste à faire remonter
progressivement les plus grands éléments d'un tableau, comme les bulles d'air remontent à la
surface d'un liquide. L'algorithme parcourt le tableau, et compare les couples d'éléments successifs.
Lorsque deux éléments successifs ne sont pas dans l'ordre croissant, ils sont échangés. Après chaque
parcours complet du tableau, l'algorithme recommence l'opération. Lorsqu'aucun échange n'a lieu
pendant un parcours, cela signifie que le tableau est trié. On arrête alors l'algorithme.

En pseudo-code, l’algorithme s’écrit ainsi:

 Mohamed Bécha Kaâniche - oct.-10

Bubble-sort (A)
Begin
repeat
no-swap = true
for i = 1 to n - 1 do
if A[i] > A[i+1] then swap( A[i], A[i+1] )
no-swap = false
until ( no-swap)
End

Version récursive (appel initial Bubble-sort-recursive (A, n)) :

Bubble-sort-recursive (A,n)
Begin
swapped = false
for i = 1 to n - 1 do
if A[i] > A[i+1] then swap( A[i], A[i+1] )
swapped = true
if(swapped) then Bubble-sort-recursive (A, n);
End

Questions

1. Calculez la complexité de cet algorithme au meilleur cas, au pire cas et en moyenne des cas en
nombre de comparaisons.
2. Que peut-on dire sur sa complexité en nombre d’échanges ?
3. (Bonus) Ecrivez en C++ le code relatif aux versions itérative et récursive de cet algorithme.

Tri arborescent
La méthode du tri arborescent veut mémoriser toute information obtenue à l’issu des comparaisons
pour l’exploiter dans l’établissement de l’ordre final. Pour ce faire elle construit une arborescence qui
traduit la relation qui existe entre tous les éléments. Convenons donc de mettre à gauche d'une clé
toutes celles qui lui sont inférieures, et à droite toutes celles qui lui sont supérieures, et ainsi de suite
récursivement. Ainsi le tableau ordonné est obtenu en listant les éléments depuis la racine en suivant
le pseudo-code récursif suivant (appel initial List-Elements (root)):

List-Elements(node)
Begin
if exists(node->left-sub-tree) then List-Elements(node->left-sub-tree)
List(node)
if exists(node->right-sub-tree) then List-Elements(node->right-sub-tree)
End

Questions

1. Ecrire l’algorithme « Tri arborescent » qui s’appelle lui-même selon la valeur de la clé.
2. Quelle est la complexité de cet algorithme ?

 Mohamed Bécha Kaâniche - oct.-10

Tri par fusion
L’algorithme de tri par fusion est construit suivant le paradigme « diviser pour régner » :

1. Il divise la séquence de n nombres à trier en deux sous-séquences de taille n=2.

2. Il trie récursivement les deux sous-séquences.
3. Il fusionne les deux sous-séquences triées pour produire la séquence complète triée.

La récursion termine quand la sous-séquence à trier est de longueur 1... car une telle séquence est
toujours triée.

La principale action de l’algorithme de tri par fusion est justement la fusion des deux listes triées. Le
principe de cette fusion est simple : à chaque étape, on compare les éléments minimaux des deux
sous-listes triées, le plus petit des deux étant l’élément minimal de l’ensemble on le met de côté et
on recommence. On conçoit ainsi un algorithme Fusionner (Merge) qui prend en entrée un tableau A
et trois entiers, p, q et r, tels que p ≤ q < r et tels que les tableaux A[p..q] et A[q+1..r] soient triés.

Merge(A, p, q, r)
Begin
i=p Indice servant à parcourir le tableau A[p..q]
j = q+1 Indice servant à parcourir le tableau A[q+1..r]
Let C a table of size (r - p+1) Tableau temporaire dans lequel on construit le résultat
k=1 Indice servant à parcourir le tableau temporaire
while i ≤ q and j ≤ r do Boucle de fusion
if A[i] < A[ j] then C[k] = A[i]
i = i+1
else C[k] = A[ j]
j = j+1
k = k+1
while i ≤ q do C[k] = A[i] on incorpore dans C les éléments de A[p::q]
i = i+1 qui n’y seraient pas encore ; s’il y en a,
k = k+1 les éléments de A[q+1::r] sont déjà tous dans C
while j ≤ r do C[k] = A[ j] on incorpore dans C les éléments de A[q+1::r]
j = j+1 qui n’y seraient pas encore ; s’il y en a,
k = k+1 les éléments de A[p::q] sont déjà tous dans C
for k = 1 to r – p +1 do on recopie le résultat dans le tableau originel
A[p+k-1] = C[k]
End

Complexité de Fusionner (Merge)

Étudions les différentes étapes de l’algorithme :

 Les initialisations ont un coût constant (1) ;

 La boucle tant que (while) de fusion s’exécute au plus r - p fois, chacune de ses itérations
étant de coût constant, d’où un coût total en O(r - p) ;
 Les deux boucles tant que(while) complétant C ont une complexité respective au pire de q-
p+1 et de r - q, ces deux complexités étant en O(r- p) ;
 la recopie finale coûte (r- p+1).

Par conséquent, l’algorithme de fusion a une complexité en (r- p).

 Mohamed Bécha Kaâniche - oct.-10

Questions

1. Réécrivez l’algorithme de fusion vu en cours et recalculer sa complexité.

2. Exécutez à la main le tri par fusion en donnant toutes les étapes intermédiaires pour le tableau
suivant :

38 27 43 3 9 82 10 25 57 17

3. (Bonus) Ecrivez en C++ le code relatif à cet algorithme.

Tri rapide (Quick sort)

Le tri rapide est fondé sur le paradigme « diviser pour régner », tout comme le tri fusion, il se
décompose donc en trois étapes :

 Diviser : Le tableau A[p..r] est partitionné (et réarrangé) en deux sous-tableaux non vides,
A[p..q] et A[q+1..r], tels que chaque élément de A[p..q] soit inférieur ou égal à chaque
élément de A*q+1..r+. L’indice q est calculé pendant la procédure de partitionnement.
 Régner : Les deux sous-tableaux A[p..q] et A[q+1..r] sont triés par des appels récursifs.
 Combiner : Comme les sous-tableaux sont triés sur place, aucun travail n’est nécessaire pour
les recombiner, le tableau A[p..r] est déjà trié !

En pseudo-code, l’algorithme s’écrit:

Quick-sort(A, p, r)
Begin
if p < r then q = PARTITIONNING (A, p, r)
Quick-sort(A, p, q)
Quick-sort(A, q+1, r)
End

L’appel Quick-sort(A, 1, length(A)) trie le tableau A. Le point principal de l’algorithme est bien
évidemment le partitionnement qui réarrange le tableau A sur place :

PARTITIONNING (A, p, r)
Begin
x = A[p]
i = p-1
j = r+1
while true do
repeat j = j-1 until A[ j] <= x
repeat i = i+1 until A[i] >= x
if i < j then swap(A[i],A[ j])
else return j
End

Exemple de partitionnement :

 Mohamed Bécha Kaâniche - oct.-10

 Situation initiale :
1 2 3 4 5 6 7
4 3 6 2 1 5 7
Nous avons donc x = 4, i = 0 et j = 8.

 On exécute la boucle « repeat j = j-1 until A[ j] <= x » et on obtient j = 5.

 On exécute la boucle « repeat i = i+1 until A[i] >= x », et on obtient i = 1.
 Après l’échange on obtient le tableau :
1 2 3 4 5 6 7
1 3 6 2 4 5 7

 On exécute la boucle « repeat j = j-1 until A[ j] <= x » et on obtient j = 4.

 On exécute la boucle «repeat i = i+1 until A[i] >= x », et on obtient i = 3.
 Après l’échange on obtient le tableau :
1 2 3 4 5 6 7
1 3 2 6 4 5 7

 On exécute la boucle «repeat j = j-1 until A[ j] <= x » et on obtient j = 3.

 On exécute la boucle «repeat i = i+1 until A[i] >= x », et on obtient i = 3.
 Comme i = j, l’algorithme se termine et renvoie la valeur « 3 ».

Complexité

Pire cas

Le pire cas intervient quand le partitionnement produit une région à n-1 éléments et une à un
élément. Comme le partitionnement coûte (n) et que T(1) = (1), la récurrence pour le temps
d’exécution est : T(n) = T(n-1) + (n) D’où par sommation :

  

Meilleur cas

On subodore que le meilleur cas apparaît quand la procédure de partitionnement produit deux
régions de taille n/2 .

La récurrence est alors : T(n) = 2 T(n/2)+  (n) ce qui, d’après le cas 2 du théorème 1 nous donne :
T(n) = (nlogn)

Complexité en moyenne

Pour avoir une complexité moyenne, on tire au hasard l’indice de départ de partitionnement. Et on
démontre que la complexité moyenne et aussi égale à : T(n) = (nlogn)

Questions

1. Exécuter à la main l’algorithme du tri rapide en prenant comme tableau celui illustrant la
première invocation de la fonction PARTITIONNING.

 Mohamed Bécha Kaâniche - oct.-10

Tri par tas
L'idée qui sous-tend cet algorithme consiste à voir le tableau comme un arbre binaire. Le premier
élément est la racine, le deuxième et le troisième sont les deux descendants du premier élément,
etc. Ainsi le nème élément a pour enfants les éléments 2n et 2n + 1. Si le tableau n'est pas de taille
(2n − 1), les branches ne se finissent pas toutes à la même profondeur.

Dans l'algorithme, on cherche à obtenir un tas (Heap en anglais), c'est-à-dire un arbre binaire
vérifiant les propriétés suivantes (les deux premières propriétés découlent de la manière dont on
considère les éléments du tableau) :

 La différence maximale de profondeur entre deux feuilles est de 1 (i.e. toutes les feuilles se
trouvent sur la dernière ou sur l'avant-dernière ligne)
 Les feuilles de profondeur maximale sont « tassées » sur la gauche.
 Chaque nœud est de valeur supérieure (resp. inférieure) à celles de ses deux fils, pour un tri
ascendant (resp. descendant).

Un tas ou un arbre binaire presque complet peut être stocké dans un tableau, en posant que les deux
descendants de l'élément d'indice n sont les éléments d'indices 2n et 2n + 1 (pour un tableau indicé à
partir de 1). En d'autres termes, les nœuds de l'arbre sont placés dans le tableau ligne par ligne,
chaque ligne étant décrite de gauche à droite.

Une fois le tas de départ obtenu, l'opération de base de ce tri est le tamisage, ou percolation, d'un
élément, supposé le seul « mal placé » dans un arbre qui est presque un tas. Plus précisément,
considérons un arbre A = A[1] dont les deux sous-arbres (A[2] et A[3]) sont des tas, tandis que la
racine est éventuellement plus petite que ses fils. L'opération de tamisage consiste à échanger la
racine avec le plus grand de ses fils, et ainsi de suite récursivement jusqu'à ce qu'elle soit à sa place.

Pour construire un tas à partir d'un arbre quelconque, on tamise les racines de chaque sous-tas, de
bas en haut (par taille croissante) et de droite à gauche.

Pour trier un tableau à partir de ces opérations, on commence par le transformer en tas. On échange
la racine avec le dernier élément du tableau, et on restreint le tas en ne touchant plus au dernier
élément, c'est-à-dire à l'ancienne racine. On tamise la racine dans le nouveau tas, et on répète
l'opération sur le tas restreint jusqu'à l'avoir vidé et remplacé par un tableau trié.

Heapify(A, node ,n): {descend A[node] à sa place, sans dépasser l'indice n}

Begin
k = node
j=2
while(j<=n)
if(j<n and A[j]< A[j+1]) then j:=j+1
if(A[k]< A[j]) then swap(A[k], A[j])
k=j
j=2k
else break ;
End

 Mohamed Bécha Kaâniche - oct.-10

Heapsort(A,length)
Begin
for i = length /2 to 1 step -1 do
Heapify (A,i, length)
for i = length to 2 step -1 do
swap(A[i], A[1])
Heapify (A,1,i-1)
End

Questions

1. Quelle est la complexité de cet algorithme de tri ?

 Mohamed Bécha Kaâniche - oct.-10