Cours 3

Cours :
Algorithmique avancée
Algorithmes de tri
Algorithmes de tri
Problématique :
-Etant donné une structure linéaire (tableau, liste, etc)

contenant des valeurs d'un type ordonné, il faut trier les
éléments en ordre croissant (ou décroissant).
- Il existe des dizaines d'algorithmes répondant à ce problème,

utilisant quelques principes de base auxquels on ajoute des
variantes .
Algorithmes de tri
 On peut distinguer :
 les tris internes qui trient les éléments dans la

structure qui les contient (tableau, liste, ...) ou au pire
utilise une structure annexe de même type.
 les tris externes utilisés lorsque la quantité

d'éléments à trier est telle qu'ils ne tiennent pas en
mémoire vive et qu'il faut stocker des éléments dans
des fichiers ou des tables de bases de données.
Algorithmes de tri
 La plupart des algorithmes de tri utilisent la comparaison d'éléments
2à2:
 le nombre minimum de comparaisons à effectuer est

n*log(n) si n est la taille de la structure.
 Les algorithmes en O(n2 ) sont donc peu efficaces, ceux

au pire en O(n*log(n)) sont optimaux.
ilexiste des tris linéaires, mais ils n'utilisent pas la

comparaison et sont limités à des cas très
particuliers (tris de nombres dont on connait des
propriétés statistiques)
Tri par sélection
Trouver le plus petit élément et le mettre au début

de la liste
Trouver le 2e plus petit et le mettre en seconde

position
Trouver le 3e plus petit élément et le mettre à la

3e place,

...
Tri par sélection
Tri par sélection
Le tri par insertion
(le tri du joueur de cartes !)
Ordonner les deux premiers éléments

Insérer le 3e élément de manière à ce que les 3 premiers
éléments soient triés
Insérer le 4e élément à “sa” place pour que …
. . .
Insérer le ne élément à sa place.
A la fin de la ie itération, les i premiers éléments de T sont triés et

rangés au début du tableau T′ .
Le tri par insertion
Tri par fusion
 Principe du tri fusion :

on découpe le tableau en deux, on trie chacune des 2
parties, puis on fusionne les parties triées en respectant
l'ordre.
 Algorithme:
La principale action de l’algorithme de tri par fusion est justement
la fusion des deux listes triées.
Fusion:
Fusion:
Tri par fusion
Tri par fusion
Algorithme : il nous faut donc
 une fonction qui fusionne deux sections contigues du
tableau.
 une fonction de tri proprement dit qui lance des appels
récursifs sur les sous parties puis appelle la fonction

précédente.
• Il s’agit d’un algorithme “diviser-pour- régner”

Tri par fusion
Tri par fusion
// cette fonction fusionne les parties de tab d'indices dans [a,b] et [b+1,c],
// en supposant que les éléments de ces parties soient triés en ordre croissant.
Complexité du tri-fusion :
la complexité de la fusion est linéaire de la forme a*n où a est

une constante.
 la complexité du tri est c(n) = c(n/2) + c(n/2) + a*n + b où b est

une constante donc c(n) = O(n*log(n)) dans tous les cas.
 Le tri fusion est donc optimum en complexité.

Le tri rapide
Un autre tri récursif. . . plus efficace en pratique.
Etant donne un tableau de T[1, . . . , n] :
•si n = 1, retourner le tableau T
•sinon :
• Choisir un élément (le “pivot”) p dans T
• Placer les éléments inferieurs à p au début de T
• Placer p à sa place dans T
• Placer les éléments supérieurs à p à la fin de T
• Trier la première partie de T puis la seconde. . .
(plus de fusion !)
Le tri rapide
Algorithme :
On partitionne le tableau autour de la valeur contenue dans la première

case, puis on appelle l'algorithme sur chacune des sous-parties.
Il nous faut donc :
 une fonction qui partitionne une certaine section [a,b] du tableau en

plaçant au début les éléments plus petits que tab[a], puis tab[a], puis les
éléments plus grands ou égaux à tab[a] et retourne l'indice de tab[a] dans
le tableau partitionné (au départ, a vaudra 0 et b vaudra tab.longueur-1)
 une fonction de tri proprement dit qui appelle la fonction

précédente puis lance des appels récursifs sur les sous-parties
Le tri rapide
Le tri rapide
Algorithme :
Complexité du tri rapide :
 la fonction de partitionnement est linéaire de la forme a*n où
a est une constant.
 au mieux :c(n) = a*n + 2*c(n/2) + b où b est une constante.

Dans ce cas, on a c(n) = O(n*log(n))
au pire: c(n) = a*n + c(n-1) + b où b est une constante.

Dans ce cas, on a c(n) = O(n2 ).
 en moyenne: c(n) = O(n*log(n)).
 Le tri rapide n'est pas optimum dans tous les cas, mais en
moyenne, il est bien plus rapide que les tris quadratiques
Complexité du tri rapide :
Améliorations possibles :
quand le tableau est déjà « un peu trié », il vaut mieux choisir

comme pivot l'élément du milieu du tableau, pour équilibrer les
parties.
quand le tableau n'est pas « un peu trié », on peut découvrir

l'élément médian avec un algorithme linéaire. Cette amélioration
assure donc une complexité au pire en O(n*log(n)) au tri rapide.

Cours 3

Transféré par

Droits d'auteur :

Formats disponibles

Cours 3

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours 3

Transféré par

Droits d'auteur :

Formats disponibles

Cours :

-Etant donné une structure linéaire (tableau, liste, etc)

- Il existe des dizaines d'algorithmes répondant à ce problème,

 les tris internes qui trient les éléments dans la

 les tris externes utilisés lorsque la quantité

 le nombre minimum de comparaisons à effectuer est

 Les algorithmes en O(n2 ) sont donc peu efficaces, ceux

ilexiste des tris linéaires, mais ils n'utilisent pas la

Trouver le plus petit élément et le mettre au début

Trouver le 2e plus petit et le mettre en seconde

Trouver le 3e plus petit élément et le mettre à la

Ordonner les deux premiers éléments

Insérer le 4e élément à “sa” place pour que …

A la fin de la ie itération, les i premiers éléments de T sont triés et

 Principe du tri fusion :

récursifs sur les sous parties puis appelle la fonction

• Il s’agit d’un algorithme “diviser-pour- régner”

la complexité de la fusion est linéaire de la forme a*n où a est

 la complexité du tri est c(n) = c(n/2) + c(n/2) + a*n + b où b est

 Le tri fusion est donc optimum en complexité.

Etant donne un tableau de T[1, . . . , n] :

•si n = 1, retourner le tableau T

On partitionne le tableau autour de la valeur contenue dans la première

Il nous faut donc :

 une fonction qui partitionne une certaine section [a,b] du tableau en

 une fonction de tri proprement dit qui appelle la fonction

 au mieux :c(n) = a*n + 2*c(n/2) + b où b est une constante.

au pire: c(n) = a*n + c(n-1) + b où b est une constante.

 en moyenne: c(n) = O(n*log(n)).

quand le tableau est déjà « un peu trié », il vaut mieux choisir

quand le tableau n'est pas « un peu trié », on peut découvrir

Vous aimerez peut-être aussi

 au mieux :c(n) = an + 2c(n/2) + b où b est une constante.