Chapitre iv algorithmes de tri

CHAPITRE IV:

ALGORITHMES DE TRI

Université Saad Dahleb de Blida

Faculté des Sciences

Département d’Informatique

Licence Génie des Systèmes Informatique (GSI)

Semestre 5 (3ème année)

ALGORITHMIQUE 02

Cours n°7: 30 Octobre 2013

AROUSSI Sana

Disponible sur https://sites.google.com/a/esi.dz/s-aroussi/

https://sites.google.com/a/esi.dz/s-aroussi/



PLAN DU CHAPITRE IV

Introduction

Tri par Sélection

Tri par Insertion

Tri par Propagation

Tri par Fusion

Tri Rapide

Tri par ABR (Arbre Binaire de Recherche)

Tri par TAS

Conclusion

2

3

É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é.

INTRODUCTION

4

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 PRINCIPE

7 3 18 13 7 7 3 18 13 7 3 7 18 13 7

3 7 18 13 7 3 7 7 13 18 3 7 7 13 18

3 7 7 13 18

5

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

TRI PAR SÉLECTION ALGORITHME RÉCURSIF

6

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

Debut

min debut

Pour idebut +1 à fin faire

Si (T[i] < T[min]) alors min i;

Rechercher_min min;

Fin

TRI PAR SÉLECTION FONCTION « RECHERCHER_MIN »

7

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

Debut

min debut

Pour idebut +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 »

Nombre d’itération =

Fin

Nombre d’itération =

Fin – debut = n-1

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

C1 C1

C3 C3

8

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

TRI PAR SÉLECTION COMPLEXITÉ

T (n) tq n = fin – debut + 1 T (n) tq n = fin – debut + 1

T (n - 1) T (n - 1)

C1 C1

Tmin (n) Tmin (n)

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

9

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 ie itération, les i

premiers éléments de T sont triés et rangés au début du

tableau T′

TRI PAR INSERTION PRINCIPE

7 3 18 13 7 3 7 18 13 7 3 7 18 13 7

3 7 13 18 7 3 7 7 13 18 3 7 7 13 18

10

Tri_Insertion (T: tableau, n : entier)

Debut

Si (n>1) alors

Tri_Insertion(T,n-1);

Insérer (T, n) // insérer le nème élément à sa place dans le tableau T[1..n-1]

FSI

Fin

TRI PAR INSERTION ALGORITHME RÉCURSIF

11

Inserer (T: tableau, n : entier)

Debut

in-1

Tant que (i>0 et T[i]>T[i+1]) faire

DTQ

Permuter (i+1, i)

i i-1

FTQ

FSI

Fin

TRI PAR INSERTION PROCÉDURE « INSÉRER »

12

Inserer (VAR T: tableau, n : entier)

Debut

in-1

Tant que (i>0 et T[i]>T[i+1]) faire

DTQ

Permuter (i+1, i)

i i-1

FTQ

FSI

Fin

TRI PAR INSERTION COMPLEXITÉ DE LA PROCÉDURE « INSÉRER »

Pire des cas que le n élément

contient la valeur la plus petite

et dans ce cas on doit parcourir

tous le tableau

d’itération maximal = n

Pire des cas que le nème élément

contient la valeur la plus petite

et dans ce cas on doit parcourir

tous le tableau Nombre

d’itération maximal = n-1

T (n) = C1 n + C2 O(T ) = O (n) Tinsérer (n) = C1 n + C2 O(Tinsérer) = O (n)

13

Tri_Insertion (T: tableau, n : entier)

Debut

Si (n>1) alors

Tri_Insertion(T,n-1);

// insérer le n-ème élément dans le tableau T[1..n-1] :

Insérer (T, n)

FSI

Fin

TRI PAR INSERTION COMPLEXITÉ

T (n) tq n taille du tableau T (n) tq n taille du tableau

T (n - 1) T (n - 1)

T (n ) Tinsérer (n )

T (n) = T(n-1) + T (n ) T (n) = T(n-1) + Tinsérer (n ) O(T) = O (n ) O(T) = O (n2)

14

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 PRINCIPE

7 3 18 13 7 3 7 18 13 7 3 7 18 13 7

3 7 13 18 7 3 7 13 7 18

3 7 7 13 18

3 7 13 7 18

3 7 13 7 18 3 7 7 13 18

15

Tri_Propagation (T: tableau, n : entier)

Debut

Si non Trier (T, n) alors

DSI

Pour i 1 à n-1 faire

Si T[i] > T[i+1] alors permuter (T[i], T(i+1))

// La dernière case contient toujours l’élément le plus grand

Tri_Propagation (T, n-1)

FSI

Fin

TRI PAR PROPAGATION ALGORITHME RÉCURSIF

16

Fonction Trier (T: tableau, n : entier) : Booléen;

Debut

Ok vrai; i 1;

Tant que (i <n et non OK) faire

DTQ

Si T[i]>T[i+1] alors okfaux

ii+1

FTQ

Trier OK

Fin

TRI PAR PROPAGATION FONCTION « TRIER »

17

Fonction Trier (T: tableau, n : entier) : Booléen;

Debut

Ok vrai; i 1;

Tant que (i <n et non OK) faire

DTQ

Si T[i]>T[i+1] alors okfaux

ii+1

FTQ

Trier OK

Fin

TRI PAR PROPAGATION COMPLEXITÉ DE LA FONCTION « TRIER »

Pire des cas que le tableau soit

trié et dans ce cas on parcourt

tous le tableau

d’itération maximal = n

Pire des cas que le tableau soit

trié et dans ce cas on parcourt

tous le tableau Nombre

d’itération maximal = n-1

T (n) = C1 n + C2 O(T ) = O (n) Ttrier (n) = C1 n + C2 O(Ttrier) = O (n)

18

TRI PAR PROPAGATION COMPLEXITÉ

T (n) Ttrier (n)


T (n-1) T (n-1)

T (n) = T(n-1) + T (n) + c1(n-1) + c2 T (n) = T(n-1) + Ttrier (n) + c1(n-1) + c2 O(T) = O (n ) O(T) = O (n2)

n-1 fois n-1 fois

Tri_Propagation (T: tableau, n : entier)

Debut

Si non Trier (T, n) alors

DSI

Pour i 1 à n-1 faire

Si T[i] > T[i+1] alors permuter (T[i], T(i+1))

// La dernière case contient toujours l’élément le plus grand

Tri_Propagation (T, n-1)

FSI

Fin

19

Le principe est de trier deux tableaux de taille N/2 et

ensuite de les fusionner de sorte à ce que le tableau final

soit trié.

TRI PAR FUSION PRINCIPE

7 3 18 13 7

7 3 18 13 7

7 13 18

3 7 7 10 13 18

7

3 7

3 18 13 7

7 13

13 7

20

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 reste trie

TRI PAR FUSION PARADIGME DIVISER POUR RÉGNER

21

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 ALGORITHME RÉCURSIF

22

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++;

// recopier le tableau

Pour idebut à fin faire T[i]=tmp[i]

Fin

TRI PAR FUSION PROCÉDURE « FUSIONNER »

23

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++;

// recopier le tableau

Pour idebut à fin faire T[i]=tmp[i]

Fin

TRI PAR FUSION COMPLEXITÉ DE LA PROCÉDURE « FUSIONNER »

T (n) tq n= fin – debut +1 Tfusionner(n) tq n= fin – debut +1

n fois n fois

n fois n fois

T (n) = c1 * n + c2 O (T ) = O (n) Tfusionner(n) = c1 * n + c2 O (Tfusionner) = O (n)

24

TRI PAR FUSION COMPLEXITÉ

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

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


T (n/2) T (n/2)

T (n/2) T (n/2)

T (n) Tfusionner(n)

CHAPITRE IV:

ALGORITHMES DE TRI






ALGORITHMIQUE 02

Cours n°8: 3 Novembre 2013

AROUSSI Sana





26

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 PRINCIPE

27

DIVISER: Diviser le tableau en deux tableaux selon le

pivot choisi : T1[debut..pivot] 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 PARADIGME DIVISER POUR RÉGNER

28

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

Debut

SI debut < fin alors

Pivotpartitionner(T, debut, fin , pivot)

Tri_Rapide(T, debut, pivot)

Tri_Rapide(T, pivot+1, fin)

FSI

Fin

TRI RAPIDE ALGORITHME RÉCURSIF

29

Partitionner (T: tableau, debut, fin, pivot: entier): entier

Debut

permuter (T[pivot], T[fin])

j premier

Pour i 1 à 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 FONCTION « PARTITIONNER »

30


Debut


j premier




j j + 1

FSI

FP


Partitionner j

Fin

TRI RAPIDE FONCTION « PARTITIONNER »

31


Debut


j premier




j j + 1

FSI

FP


Partitionner j

Fin

TRI RAPIDE COMPLEXITÉ DE LA FONCTION « PARTITIONNER »

T (n) tq n= fin – debut +1 Tpartitionner(n) tq n= fin – debut +1

Pire de cas: n-1 fois Pire de cas: n-1 fois

T (n) = c1 * n + c2 O(T ) = O (n) Tpartitionner(n) = c1 * n + c2 O(Tpartitionner) = O (n)

32

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

Debut

SI debut < fin alors

Pivotpartitionner(T, debut, fin , pivot)

Tri_Rapide(T, debut, pivot)

Tri_Rapide(T, pivot+1, fin)

FSI

Fin

TRI RAPIDE COMPLEXITÉ

T(n)/ n= fin – debut +1 T(n)/ n= fin – debut +1

T (n) Tpartitionner(n)

T(pivot-debut+1) T(pivot-debut+1)

T(fin-pivot) T(fin-pivot)

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

33

TRI RAPIDE CHOIX DU PIVOT ET COMPLEXITÉ


Cas 1: Pivot aléatoire. 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.

34

TRI RAPIDE CHOIX DU PIVOT ET COMPLEXITÉ


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 log2 n)

CHAPITRE IV:

ALGORITHMES DE TRI






ALGORITHMIQUE 02


AROUSSI Sana





36

TRI PAR ABR DÉFINITION

Un Arbre Binaire de Recherche (ABR) est un arbre

binaire, dans lequel chaque nœud contient un entier en

respectant la propriété suivante :

Inférieur (ou égal) aux entiers de son sous-arbre gauche

Supérieur strictement aux entiers de son sous-arbre droit

37

TRI PAR ABR PRINCIPE

1. Insérer toutes les éléments du tableau dans un

ABR

20 15 10 35 19 13 5 3 12 7 16 40 25 38

20

15 35

10

19

5 13

3 7 12

25 40

38

16

38

TRI PAR ABR PRINCIPE

2. Parcourir l’ABR en ordre infixé: fils gauche, nœud,

fils droit

3 5 7 10 12 13 15 16 19 20 25 35 38 40

20

15 35

10

19

5 13

3 7 12

25 40

38

16

39

TRI PAR ABR ALGORITHME ITÉRATIF

Soit AR un arbre de recherche binaire

Tri_ARB_IT (T: Tableau, n: entier)

Debut

// Construire ARB

ARNil

Pour i1 à n faire

ARInsérer (AR, T[i]).

Parcours_Infixe (AR, T); //Parcours Infixe

Fin

40

TRI PAR ABR FONCTION « INSÉRER »

Insérer (AR: nœud , x: entier): nœud

Debut

SI (AR=Nil) alors // L’arbre est vide

AR Noeud(x,Nil,Nil) // Créer la racine (le premier nœud)

SINON

SI x ≤ valeur(AR) alors

AR.FGInsérer(x, FG(AR)) // Insérer à gauche

SINON

AR.FDInsérer(x, FD(AR)) // Insérer à droite

FSI

Insérer AR

Fin

41

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)

20 20

15 15 35 35

10 10 19 19

5 5 13 13

3 3 7 7 12 12

25 25 40 40

38 38 16 16

h=4 h=4

h=3 h=3

h=2 h=2

h=1 h=1

h=0 h=0

h = 4

n = 14

42

TRI PAR ABR COMPLEXITÉ DE LA FONCTION « INSÉRER »

T (h) tq h est la hauteur de l’arbre Tinsérer (h) tq h est la hauteur de l’arbre

T (h +1) Tinsérer (h +1)

T (h +1) Tinsérer (h +1)

Tinsérer (h+1) = Tinsérer (h) + c O(Tinsérer ) = O (h)

Insérer (AR: nœud , x: entier): nœud

Debut

SI (AR=Nil) alors // L’arbre est vide

AR Noeud(x,Nil,Nil) // Créer la racine (le premier nœud)

SINON

SI x ≤ valeur(AR) alors

AR.FGInsérer(x, FG(AR)) // Insérer à gauche

SINON

AR.FDInsérer(x, FD(AR)) // Insérer à droite

FSI

Insérer AR

Fin

43

TRI PAR ABR COMPLEXITÉ DE LA FONCTION « INSÉRER »

O(Tinsérer) = O (h)

Pire de cas: un tableau déjà trié Arbre mal

équilibré h = n-1 O(Tinsérer) = O(n-1) = O(n)

25 25

18 18

15 15

5 5

2 2 h=4 h=4

h=3 h=3

h=2 h=2

h=1 h=1

h=0 h=0

25 18 15 5 2

44

TRI PAR ABR PARCOURS INFIXÉ

Soit « indice » une variable globale initialisé à 1

Parcours_Infixe (AR: nœud, T: Tableau)

Debut

Si ( AR Nil) alors //Arbre n’est pas vide

Parcours_Infixe(FG(AR, T, indice))

T[indice]valeur (AR) //Écrire la valeur dans le tableau

Indice indice + 1;

Parcours_Infixe(FD(AR), T, indice)

FSI

Fin

45

TRI PAR ABR COMPLEXITÉ DU PARCOURS INFIXÉ

Soit « indice » une variable globale initialisé à 1

Parcours_Infixe (AR: nœud, T: Tableau)

Debut

Si ( AR Nil) alors //Arbre n’est pas vide

Parcours_Infixe(FG(AR, T, indice))

T[indice]valeur (AR) //Écrire la valeur dans le tableau

Indice indice + 1;

Parcours_Infixe(FD(AR), T, indice)

FSI

Fin

T (n) tq n le nombre des nœuds Tinfixe (n) tq n le nombre des nœuds

T (k) Tinfixe (k)

T (n-k-1) Tinfixe (n-k-1)

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

46

TRI PAR ABR COMPLEXITÉ DU PARCOURS INFIXÉ


É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) = a k + b + a (n-k-1) + b + c = a n + (2 b –a + c)

Tinfixe (n) = a n + d O(Tinfixe) = O(n) ..........................CQFD

47

TRI PAR ABR COMPLEXITÉ DE L’ALGORITHME ITÉRATIF

T (n) Tinfixe (n)

T (n) Tinsérer (n)

n fois n fois

T (n) TARB (n)

O(TARB)= n * O (n) + O (n)

= O (n2) + O(n)

= O(n2)

Soit AR un arbre de recherche binaire

Tri_ARB_IT (T: Tableau, n: entier)

Debut

// Construire ARB

ARNil

Pour i1 à n faire

ARInsérer (AR, T[i]).

Parcours_Infixe (AR, T); //Parcours Infixe

Fin

48

TRI PAR ABR ALGORITHME RÉCURSIF

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

Debut

SI (n>0) alors

Insérer (ARB, T[n])

Tri_ABR(T, n-1, AR)

SINON // n=0 l’arbre est construit en totalité

Parcours_Infixe (AR, T);

FSI

Fin

49

TRI PAR ABR COMPLEXITÉ DE L’ALGORITHME RÉCURSIF

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

Debut

SI (n>0) alors

Insérer (ARB, T[n])

Tri_ABR(T, n-1, AR)

SINON // n=0 l’arbre est construit en totalité

Parcours_Infixe (AR, T);

FSI

Fin

T (n) TARB (n)

T (n) Tinfixe (n)

T (n) Tinsérer (n)

T (n-1) TARB (n-1)

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

CHAPITRE IV:

ALGORITHMES DE TRI






ALGORITHMIQUE 02


AROUSSI Sana





51

TRI PAR TAS DÉFINITION

Un TAS 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)

52

TRI PAR TAS TASMIN

Minimum Minimum

Maximum Maximum

4

5 6

20 7

8 11

9 15

25 25 16 12 14

53

TRI PAR TAS TASMAX

Maximum Maximum

Maximum Maximum

40 40

35 26

20 17

8 11

19 15

13 1 12 14

54

TRI PAR TAS HAUTEUR D’UN TAS

Théorème: Un tas de n nœud a une hauteur O(log2 n)

Démonstration

Soit h, la hauteur d’un tas de n nœud

h=0 ; n = 2h=0 ; n0 = 20

h=1 ; n = 2 h=1 ; n1 = 21

h=2 ; n = 2 h=2 ; n2 = 22

h=3 ; n = 2 h=3 ; n3 = 23

55

TRI PAR TAS HAUTEUR D’UN TAS

Théorème: Un tas de n nœud a une hauteur O(log2 n)

Démonstration

Soit h, la hauteur d’un tas de n nœud

Au niveau ih, ni=2i

Donc n = 20 + 21 + 22 + ....+ 2h-1 + c tel que , 0c<2h

n = 2h + c 2h h log2 n O(h) = O(log2 n).

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

O (log2 n)

56

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.

1 2 3 4 5 6 7 8 9 10 11 12 13

4 5 6 15 9 7 20 16 25 14 12 11 8

4

5 6

20 7

8 11

9 15

25 16 12 14

1 1 2 2 3 3

4 4 5 5 6 6 7 7

8 8 9 9

57

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]

1 2 3 4 5 6 7 8 9 10 11 12 13

4 5 6 15 9 7 20 16 25 14 12 11 8

58

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

4

5 6

20 7

8 11

9 15

25 16 12 14

4 5 6 15 9 7 20 16 25 14 12 11 8

4 5 6 15 9 7 20 16 25 14 12 11 8 3

4

5 6

20 7

8 11

9 15

25 16 12 14 3

4 5 6 15 9 7 3 16 25 14 12 11 8 20

4

5 6

3 7

8 11

9 15

25 16 12 14 20

4 5 3 15 9 7 6 16 25 14 12 11 8 20

4

5 3

6 7

8 11

9 15

25 16 12 14 20

3 5 4 15 9 7 6 16 25 14 12 11 8 20

3

5 4

6 7

8 11

9 15

25 16 12 14 20

60

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, i/2)

i i/2

Fin

61

TRI PAR TASMIN EXTRAIRE MINIMUM

Le minimum se trouve à la racine.

Pour supprimer la racine:

1. Remplacer la racine par le dernier élément « v » (à la fin du

tableau).

2. Tant que la valeur « v » est supérieure à celle de l’un de ses fils,

échanger la valeur « v » avec celle du plus petit de ses fils.

Exemple : 4

5 6

20 7

26 11

9 15

25 16 12 14

4 5 6 15 9 7 20 16 25 14 12 11 8

4 5 6 15 9 7 20 16 25 14 12 11 26

4

5 6

20 7

26 11

9 15

25 16 12 14

5

26 6

20 7

11

9 15

25 16 12 14

26

5 6

20 7

11

9 15

25 16 12 14

26 5 6 15 9 7 20 16 25 14 12 11

5 26 6 15 9 7 20 16 25 14 12 11

5

9 6

20 7

11

26 15

25 16 12 14

5 9 6 15 26 7 20 16 25 14 12 11 62

5

9 6

20 7

11

26 15

25 16 26 14

5 9 6 15 12 7 20 16 25 14 26 11

5

26 6

20 7

11

9 15

25 16 12 14

5 26 6 15 9 7 20 16 25 14 12 11

5

9 6

20 7

11

26 15

25 16 12 14

5 9 6 15 26 7 20 16 25 14 12 11

63

64

TRI PAR TASMIN EXTRAIRE MINIMUM

ExtraireMin (Tas: tableau, n : entier )

Début

Tas [1] T[n];

min 1; Sortie vrai

TQ (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, min)

Sinon Sortie vrai

Fin

TRI PAR TASMIN PRINCIPE

1. Transformer le tableau en un TASMIN

20 15 10 35 19 13 5 3 12 7 16 40 25 38

20

15

15

20 10

10

20 15

35 19

10

19 15

35 20 13 10

19 13

35 20 15 5

5

19 10

35 20 15 13

3

3

5 10

19 20 15 13

35 12 65


1. Transformer le tableau en un TASMIN

20 15 10 35 19 13 5 3 12 7 16 40 25 38

3

5 10

12 20 15 13

35 19 7

3

5 10

12 7 15 13

35 19 20 16 40 25 38

66

67


2. Extraire n fois le minimum du tas:

3 5

3

5 10

12 7 15 13

35 19 20 16 40 25 38

5

7 10

12 16 15 13

35 19 20 38 40 25

68



3 5 7 10

7

12 10

19 16 15 13

35 25 20 38 40

10

12 13

19 16 15 40

35 25 20 38

69



3 5 7 10 12 13 15

12

16 13

19 20 15 40

35 25 38

13

16 15

19 20 38 40

35 25

15

16 25

19 20 38 40

35

70



3 5 7 10 12 13 15 16 19 20 25 35 38 40

16

19 25

35 20 38 40

19

20 25

35 40 38

20

35 25

38 40

25

35 40

38

35

38 40

38

40

40

71

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 i1 à n faire

T[i] TAS[1]

Extraire_Minimum (TAS, n)

Fin

72

TRI PAR TASMIN COMPLEXITÉ DE L’ALGORITHME ITÉRATIF


Début

//Construire le TAS

Pour i 1 à n faire



Pour i0 à n-1 faire

T[i+1] TAS[1]

Extraire_Minimum (TAS, n-i)

Fin

T (n) tq n la taille du tableau TTAS (n) tq n la taille du tableau

T ?? TInsérer ??

T ?? Textraire??

73

TRI PAR TASMIN COMPLEXITÉ DE LA PROCÉDURE INSÉRER_TAS

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, i/2)

i i/2

Fin

Pire des cas: le n+1

tableau est le minimum

le nombre d’itération de la boucle

égale à log

Pire des cas: le n+1 ème élément du

tableau est le minimum

le nombre d’itération de la boucle

égale à log2(n+1)

T (n) TInsérer(n)

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

74

TRI PAR TASMIN COMPLEXITÉ DE LA PROCÉDURE EXTRAIRE_MINIMUM

Extraire_Minimum (Tas: tableau, n : entier )

Début

Tas [1] T[n];

min 1; Sortie vrai

TQ (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, min)

Sinon Sortie vrai

Fin

Pire des cas: le dernier

élément est le maximum

correspond à la hauteur de

l’arbre donc égale à log

Pire des cas: le dernier

élément est le maximum

le nombre d’itération

correspond à la hauteur de

l’arbre donc égale à log2 n

T (n) TExtraire(n)

TExtraire (n) = c3 log2(n) + c4 O(TExtraire ) = O(log2(n) )

75

TRI PAR TASMIN COMPLEXITÉ DE L’ALGORITHME ITÉRATIF


Début

//Construire le TAS

Pour i 1 à n faire



Pour i0 à n-1 faire

T[i+1] TAS[1]


Fin

T (n) tq n la taille du tableau TTAS (n) tq n la taille du tableau

T (i-1) = log (i) + c2 log (i) TInsérer (i-1) = log2(i) + c2 log2(i)

T (n-i) = log (n-i) + c4 log (n-i) Textraire (n-i) = log2(n-i) + c4 log2(n-i)

O(TTAS ) = O(nlog2(n) )

76

ALGORITHME RÉCURSIF

i1; phase1

Tri_TASmin (T, TAS: Tableau, n, i, phase: entier)

Début

Si Phase = 1 alors //Construire le TAS

Si (i<=n) alors


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]



Fsi

Fin

77

COMPLEXITÉ DE L’ALGORITHME RÉCURSIF

i1; phase1

Tri_TASmin (T, TAS: Tableau, n, i, phase: entier)

Début

Si Phase = 1 alors //Construire le TAS

Si (i<=n) alors



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]



Fsi

Fin

T (m) tq m= n-i+1 la taille effective du tableau (m n) TTAS (m) tq m= n-i+1 la taille effective du tableau (m n)

O(T ) = O(log (n-m+1)) O(TInsérer ) = O(log2(n-m+1))

O(T ) = O(log (m-1)) O(Textraire) = O(log2(m-1))

O(TTAS ) = O(nlog2(n) )

T (m-1) TTAS (m-1)

T (m-1) TTAS (m-1)

78

CONCLUSION

Algorithme de Tri Complexité au Pire

Tri par Sélection O(n2)

Tri par Insertion O(n2)

Tri par Propagation O(n2)

Tri par ABR O(n2)

Tri Rapide O(n2)

O(nlog2(n))

Tri par Fusion O(nlog2(n))

Tri par TAS O(nlog2(n))

79

EXERCICE

Réécrire les algorithmes de tri (vus

précédemment) afin de pouvoir trier le tableau

en ordre décroissant (plus grand au plus petit).

80

TP: TRI PAR ABRE

Un Arbre Binaire de Recherche Équilibré (ABRE), comme son nom

indique, est un arbre :

binaire de recherche : chaque nœud possède au plus deux fils

(gauche et droit), et la valeur du père est inférieur ou égale à la valeur

de son fils gauche et supérieur strictement à la valeur de son fils droit.

Équilibré : possède un critère d'équilibre spécifique par exemple :

Dans TAS, l'arbre est complet, i.e. si sa hauteur est h, les niveaux

inférieurs (0, 1, 2,...., h-1) sont entièrement remplis.

Dans un arbre AVL, les hauteurs du sous arbre gauche et celle du

sous arbre droit diffèrent au plus de un.

Dans un arbre rouge-noir, la hauteur maximum est égale à 2 log2 (n

+ 1) où n est le nombre de nœuds.

.............

81

TP: TRI PAR ABRE

Le but de ce TP est de proposer un algorithme de tri par un ABRE

permettant de classer les éléments du tableau.

Pour ce faire, les étapes suivantes doivent être respectées :

1. Conception de l’algorithme : définir la structure de l’ABRE choisi,

décrire le principe du tri, dérouler le principe sur un exemple, écrire

l’algorithme (version itérative et récursive) et enfin calculer la

complexité de l’algorithme.

2. Implémentation de l’algorithme : Développer une application sous

Java permettant, entre autre, de:

Via une interface graphique :

Saisir manuellement le tableau (la taille et les éléments), ou

Importer le tableau à partir d’un benchmark (fichier .txt)

Afficher le tableau trié

Calculer le temps d’exécution.

82

TP: TRI PAR ABRE

Pour ce faire, les étapes suivantes doivent être respectées :

1. Conception de l’algorithme

2. Implémentation de l’algorithme

3. Test : Donner le temps d’exécution dans le cas où n=10, n=100,

n=1000 (n présente la taille du tableau).

Le rapport (au maximum sur 10 pages) et

l’application (code source + exécutable .Jar sur un

CD-ROM) doivent être rendus un mois après la date

de remise du TP.

SOURCES DE CE COURS Frédéric Vivien, Algorithmique avancée, École Normale Supérieure de Lyon, 2002.,

pp. 93. Disponible sur http://perso.ens-lyon.fr/frederic.vivien/Enseignement/Algo-

2001-2002/Cours.pdf

Slim Msfar, Algorithmique et Complexité, 2012, pp 104. Disponible sur

http://p835.phpnet.org/testremorque/upload/catalogue/coursalgorithmi.pdf

Algorithmes récursifs de tri, disponible sur

http://foofish.blogspot.com/2007/01/algorithmes-rcursifs-de-tri.html

François Laroussinie Algorithmes de tri, Université Paris Diderot (Paris 7), 2010, pp

110. Disponible sur www.liafa.jussieu.fr/~francoisl/IREM/tri.pdf‎

Parcours d’un arbre binaire, disponible sur math.univ-

lyon1.fr/irem/IMG/pdf/parcours_arbre_avec_solutions-2.pdf

Olivier Bournez, Cours 7: Arbres de recherche. Tas. Disponible sur

http://www.enseignement.polytechnique.fr/informatique/INF421/Amphi-b/cours7-

handout2x2.pdf

Renaud Dumont, Algorithmique P2, HeapSort et files de priorité, 2010, pp 31,

Disponible sur www.montefiore.ulg.ac.be/~dumont/pdf/ac7.pdf‎

83

http://perso.ens-lyon.fr/frederic.vivien/Enseignement/Algo-2001-2002/Cours.pdf















































http://www.enseignement.polytechnique.fr/informatique/INF421/Amphi-b/cours7-handout2x2.pdf





















Education

Chapitre iv algorithmes de tri