Etude de cas : Problème du tri
Introduction
Le problème du tri est quasiment le plus important en
informatique.
Spécification du tri : La donnée est une liste à
n éléments ; à chaque élément est associée une clé dont la valeur
appartient à un ensemble totalement ordonné ; le résultat est une liste
dont les éléments sont une permutation de la liste d’origine, et telle que les
valeurs des clés soient croissantes quand on parcourt la liste
séquentiellement.
Un tri est stable, s’il conserve l’ordre de départ
des éléments dont les clés sont égales.
En fonction de la capacité mémoire, on distingue le tri
interne (tout en mémoire centrale) et le tri externe (mémoire
centrale + disque). Pour le tri interne, on a des algorithmes qui travaillent sur
place, c’est-à-dire sur la liste de départ et des algorithmes qui
manipulent physiquement une copie. On a des algorithmes différents et plus
compliqués quand ils se font sur place.
On compte le nombre de variables auxiliaires pour évaluer la
complexité en mémoire. Le tri interne, sur place, avec un nombre constant
de variables auxiliaires possède une bonne complexité en espace. On compte le
nombre de comparaisons entre clés et de transferts d’éléments pour évaluer la
complexité en temps.
On distingue les méthodes simples et les méthodes
plus complexes.
Tri à bulle
…
Tri par insertion
…
Tri par arbre binaire de recherche
C’est une méthode plus complexe, qui consiste à créer
l’arbre binaire de recherche, puis à faire un parcours symétrique, pour obtenir
la liste trieé.
à voire partie sur les
arbres binaires de recherche…
Quicksort
Principe
On choisit une des clés de la liste (par exemple, celle du
premier élément), et on l’utilise comme pivot. On construit sur place
une sous-liste dont les clés sont inférieures ou égales au pivot et une
sous-liste dont les clés sont strictement supérieurs au pivot.
 |
Le pivot p a alors sa place définitive. Et on
recommence récursivement sur chacune des deux sous-listes. à la fin, la liste est triée par ordre
croissant. Remarquons que le choix du pivot est délicat ; de lui dépend
l’équilibrage des deux sous listes.
On suppose donnée une procédure
Placer (e/s t : tableau de 1 à n entiers , e/ i : entier , e/ j : entier , /s k : entier)
qui effectue le traitement de t entre les indices i et j en fonction du pivot t[i], et qui rend comme résultat l’indice k où le pivot a été placé et le tableau t réagencé.
La procédure générique du quicksort s’écrit :
Procédure Quicksort (e/s t : tableau de 1 à n entiers , e/ i : entier , e/ j : entier)
utilise localement k :
entier
début
si i < j
alors début
Placer (t ,
i , j , k)
Quicksort (t , i , k - 1)
Quicksort (t , i , k - 1)
Quicksort
(t , k + 1 , j)
fin
fin
fin
Le tri de la liste complète est obtenu par Quicksort (t ,
1 , n).
La procédure Placer : La partition et le
placement du pivot ne nécessite qu’un parcours.
 |
|||||||||||
|
 |
 |
|||||||||
 |
 |
||||||||||
On utilise deux compteurs l et k qui partent
des extrémités du sous-tableau, et qui vont l’un vers l’autre :
-
l part de i+1
et avance tant que l’on rencontre un élément £ à a.
-
k part de j et
recule tant que l’on rencontre un élément > à a.
On échange les deux éléments et on recommence la progression
jusqu’à ce que les deux compteurs se croisent : la place définitive du
pivot est en k, et on y place le pivot a par échange avec un
élément £
à a.
Si on utilise la procédure Placer sur un sous-tableau
qui n’est pas à la fin de ( x = t[j+1] existe ), alors
l’élément x est un pivot placé antérieurement. Donc, on a 
. Par conséquent, cet élément x va arrêter la
progression du compteur l. Pour utiliser cette propriété (effet de bord)
lors de tous les appels, on rajoute
un terme en t[n+1] qui contiendra un élément plus grand que tous les
autres.
. Par conséquent, cet élément x va arrêter la
progression du compteur l. Pour utiliser cette propriété (effet de bord)
lors de tous les appels, on rajoute
un terme en t[n+1] qui contiendra un élément plus grand que tous les
autres.
Procédure
Placer (e/s t : tableau de 1 à n
entiers , e/ i : entier , e/ j : entier , /s k : entier)
utilise
localement l : entier
début
l
ß i +1
k
ß j
%
boucle : tant que les compteurs ne se croisent pas %
tant
que l £ k faire
début
tant
que t[k] > t[i] faire k--
tant que
t[l] £ t[i]
faire l++
%
on a t[k] £ t[i] et t[l] > t[i] %
si
l < k alors début
échanger
t[l] et t[k]
l++
k--
fin
fin
%
on met le pivot à sa place définitive %
échanger
t[i] et t[k]
fin
Complexité
Complexité de Placer : Considérons un
sous-vecteur à p éléments, on la pivot aux p - 1 autres éléments. On effectue en tout
p + 1 comparaisons.
Complexité du Quicksort, au pire: Le graphe des appels du Quicksort est un
arbre binaire. La complexité au pire en nombre de comparaisons est obtenu pour t
déjà trié est en prenant à chaque fois le 1er élément comme pivot.
Le graphe des appels sera dégénéré (peigne) et va induire une complexité au
pire en O ( n² ).
Complexité du Quicksort, en moyenne : On
suppose que les n nombres sont distincts, et que le pivot va occuper la
pième place de la liste à trier. On suppose que toutes les places
sont équiprobables ; on a la probabilité 1/n d’avoir le pivot à la
place p et donc d’avoir deux sous-listes de taille p - 1 et n
- p. On démontre (à voire cours + td ) que la complexité en moyenne est
en O (2n log n).
Taille de la pile de récursivité
Dans la procédure Quicksort, le 2ème appel est terminal, ce qui veut dire qu’on
peut le supprimer, et donc éviter des empilements. Comme un seul appel va être
conservé, on l’effectuera systématiquement sur la plus petite des deux
sous-listes. La taille de récursion sera en O (log2 n), car
on divisera par 2 la taille de la liste d’appel.
Procédure Quicksort (e/s t : tableau de 1 à n+1 entiers , e/ i : entier , e/ j : entier)
utilise localement k :
entier
début
tant que i < j
alors début
Placer (t ,
i , j , k)
% on choisit
le plus petit %
si (j - k) > (k - i)
si (j - k) > (k - i)
alors début
Quicksort
(t , i , k - 1)
i ß k
+ 1
fin
sinon début
Quicksort (t , k + 1 , j)
j ß k
- 1
fin
fin
fin
fin
Heapsort[1]
C’est un tri par sélection des minimums successifs
basé sur une structure de tas. On va obtenir un tri O (n log n) comparaisons
au pire, sans mémoire auxiliaire.
Arbres partiellement ordonnés
Un tri par sélection nécessite de savoir localiser et
récupérer efficacement ( en O (1), si possible ) le minimum parmi les
éléments non encore placés.
On considère le cas particulier du type abstrait ensemble
où les seules opérations sont :
-
l’accès à un élément
minimum
-
la suppression du minimum
-
l’adjonction d’un nouvel
élément
On représente cette ensemble par un arbre binaire parfait
partiellement ordonné.
Un arbre partiellement ordonné est un arbre étiqueté
par les valeurs d’un ensemble muni d’un ordre total, tel que la valeur
associée à tout nœud soit £ aux valeurs associées aux fils. La racine contient
toujours un élément minimum, accès en O (1).
1)
Adjonction d’un
élément x
On ajoute d’abord x comme une feuille en conservant
la structure d’arbre binaire parfait. Puis, on reconstruit l’ordre
partiel :
y ß x
tant que ( y ¹ racine ) et ( y < père(y) )
faire
échanger y et père(y)
2)
Suppression du min
Une fois la racine enlevée, on place la dernière feuille à
la racine, pour conserver la structure d’arbre binaire parfait. Puis, on
reconstruit l’ordre partiel :
y ß racine
tant que ( y n’est pas une
feuille ) et ( y n’est pas £ aux deux fils )
faire
échanger y et son fils de valeur minimum
La complexité en nombre de comparaisons de
l’adjonction et de la suppression du minimum est au pire en O (hauteur
de l’arbre). Par ailleurs, la hauteur
d’un arbre binaire parfait ayant n nœuds est de 
.
.
On utilise la représentation en tableau (ordre
hiérarchique) des arbres binaires parfaits. (à
voire partie sur les structures arborescentes) Le tableau forme le tas.
On donne les algorithmes écrits en LDA des procédure
d’adjonction et de suppression du minimum :
Procédure
ajouter ( e/s t : tableau de 1 à N entiers , e/s n : entier , e/
x : entier )
%
ajoute l’élément x à t ayant n éléments au moment de l’appel %
utilise
localement i : entier
début
si n
< N
alors début
n++
t[n] ß x
i ß n
tant que ( i > 1 ) et ( t[i] < t[i div 2] )
faire
début
échanger t[i] et t[i div 2]
i ß i
div 2
fin
fin
sinon écrire débordement du
tas
fin
Procédure
suppress_min ( e/s t : tableau de 1 à N entiers , e/s n : entier , /s
min : entier )
%
fournit dans min le minimum pour t ayant n > 0 éléments %
utilise
localement i, j : entiers
début
min ß t[1]
t[1] ß t[n]
n--
i ß 1
% tant que l’on est pas sur
une feuille %
tant que ( i £ n div 2)
faire
début
si ( n = 2i
) ou ( t[2i] < t[2i+1])
alors j ß 2i
sinon j ß 2i +1
si ( t[i] > t[j])
alors
début
échanger t[i] et t[j]
i ß j
fin
sinon exit
fin
fin
Tri par tas
Principe :
-
Construire un tas contenant
les n éléments par adjonction successives ; en O (n log n).
-
Tant que le tas n’est pas
vide, faire supprimer le minimum du tas avec réorganisation, mettre ce minimum
à sa place définitive ; en O (n log n).
La complexité en comparaison est au pire en O(n log n).
On utilise un seul tableau pour le tas et les valeurs des
minimums successifs. Le minimum à récupérer est toujours dans t[1]. On
mettra les minimums successifs à la droite du tableau, de la droite vers la
gauche. à la fin, on obtient
l’ensemble dans l’ordre décroissant.
 |
Procédure heapsort (e/s
t : tableau de 1 à n entiers)
utilise localement p,
min : entiers
début
% construction du tas %
p ß 0
tant que p < n faire
ajouter( t , p , t[p+1] )
% tri %
tant que p > 1 faire
suppress_min ( t , p , min )
t[p+1] ß min
t[p+1] ß min
fin
Remarque : l’incrémentation et la
décrémentation de p est généré par les procédures en e/s.
0 commentaires:
Enregistrer un commentaire