$MATHEMATIQUE$

INFORMATIQUE TRI

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 triée. à 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 , k + 1 , j)

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.

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

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 1^er é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 p^iè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 (log₂ 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)

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

Heapsort

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 :

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 :

yracine

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

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

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.