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/

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

É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

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

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

Si (debut < fin) alors

min rechercher_min(T, debut, fin)

Permuter (T, debut, min)

Tri_Selection (T, debut + 1, fin)

TRI PAR SÉLECTION ALGORITHME RÉCURSIF

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

min debut

Pour idebut +1 à fin faire

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

Rechercher_min min;

TRI PAR SÉLECTION FONCTION « RECHERCHER_MIN »

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

min debut

Pour idebut +1 à fin faire

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

Rechercher_min min;

TRI PAR SÉLECTION COMPLEXITÉ DE LA FONCTION « RECHERCHER_MIN »

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)

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

Si (debut < fin) alors

min rechercher_min(T, debut, fin)

Permuter (T, debut, min)

Tri_Selection (T, debut + 1, 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)

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)

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

Tri_Insertion (T: tableau, n : entier)

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]

TRI PAR INSERTION ALGORITHME RÉCURSIF

Inserer (T: tableau, n : entier)

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

Permuter (i+1, i)

TRI PAR INSERTION PROCÉDURE « INSÉRER »

Inserer (VAR T: tableau, n : entier)

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

Permuter (i+1, i)

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)

Tri_Insertion (T: tableau, n : entier)

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)

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)

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

Tri_Propagation (T: tableau, n : entier)

Si non Trier (T, n) alors

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)

TRI PAR PROPAGATION ALGORITHME RÉCURSIF

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

Ok vrai; i 1;

Tant que (i <n et non OK) faire

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

Trier OK

TRI PAR PROPAGATION FONCTION « TRIER »

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

Ok vrai; i 1;

Tant que (i <n et non OK) faire

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

Trier OK

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)

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)

Si non Trier (T, n) alors

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)

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 13 18

3 7 7 10 13 18

3 18 13 7

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

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

Si (debut<fin) alors

milieu (debut + fin) /2

Tri_Fusion(T, debut, milieu);

Tri_fusion (T, milieu + 1, fin);

Fusionner (T, debut, milieu, fin)

TRI PAR FUSION ALGORITHME RÉCURSIF

Procédure fusionner(VAR T: tableau, debut, milieu, fin: entier)

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

Tmp [i]T[droite]; droite++;

// recopier le tableau

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

TRI PAR FUSION PROCÉDURE « FUSIONNER »

Procédure fusionner(VAR T: tableau, debut, milieu, fin: entier)

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

Tmp [i]T[droite]; droite++;

// recopier le tableau

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

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

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

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)

Si (debut<fin) alors

milieu (debut + fin) /2

Tri_Fusion(T, debut, milieu);

Tri_fusion (T, milieu + 1, fin);

Fusionner (T, debut, milieu, fin)

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

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

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

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

SI debut < fin alors

Pivotpartitionner(T, debut, fin , pivot)

Tri_Rapide(T, debut, pivot)

Tri_Rapide(T, pivot+1, fin)

TRI RAPIDE ALGORITHME RÉCURSIF

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

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

Permuter (T[fin] , T[j])

Partitionner j

TRI RAPIDE FONCTION « PARTITIONNER »

j premier

j j + 1

Partitionner j

TRI RAPIDE FONCTION « PARTITIONNER »

j premier

j j + 1

Partitionner j

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)

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

SI debut < fin alors

Pivotpartitionner(T, debut, fin , pivot)

Tri_Rapide(T, debut, pivot)

Tri_Rapide(T, pivot+1, 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)

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.

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

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

TRI PAR ABR PRINCIPE

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

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

3 7 12

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

3 7 12

TRI PAR ABR ALGORITHME ITÉRATIF

Soit AR un arbre de recherche binaire

Tri_ARB_IT (T: Tableau, n: entier)

// Construire ARB

Pour i1 à n faire

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

Parcours_Infixe (AR, T); //Parcours Infixe

TRI PAR ABR FONCTION « INSÉRER »

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

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

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

SI x ≤ valeur(AR) alors

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

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

Insérer AR

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)

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

n = 14

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)

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

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

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

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

SI x ≤ valeur(AR) alors

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

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

Insérer AR

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)

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

TRI PAR ABR PARCOURS INFIXÉ

Soit « indice » une variable globale initialisé à 1

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

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)

TRI PAR ABR COMPLEXITÉ DU PARCOURS INFIXÉ

Soit « indice » une variable globale initialisé à 1

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

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)

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

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

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)

// Construire ARB

Pour i1 à n faire

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

Parcours_Infixe (AR, T); //Parcours Infixe

TRI PAR ABR ALGORITHME RÉCURSIF

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

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

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

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

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

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

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)

TRI PAR TAS TASMIN

Minimum Minimum

Maximum Maximum

25 25 16 12 14

TRI PAR TAS TASMAX

Maximum Maximum

13 1 12 14

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

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)

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

25 16 12 14

1 1 2 2 3 3

4 4 5 5 6 6 7 7

8 8 9 9

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

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

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

25 16 12 14 3

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

25 16 12 14 20

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

25 16 12 14 20

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

25 16 12 14 20

TRI PAR TASMIN INSERTION

Procédure Insérer_TAS (Tas: tableau, n, x: entier)

Début

n n + 1

Tas[i ] x

Tant que (i/2 > 0 et Tas[i/2] > x) faire

Permuter (Tas, i, i/2)

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

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

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

25 16 12 14

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

25 16 26 14

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

25 16 12 14

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

25 16 12 14

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

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

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

35 20 13 10

35 20 15 5

35 20 15 13

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

12 20 15 13

35 19 7

12 7 15 13

35 19 20 16 40 25 38

2. Extraire n fois le minimum du tas:

12 7 15 13

35 19 20 16 40 25 38

12 16 15 13

35 19 20 38 40 25

3 5 7 10

19 16 15 13

35 25 20 38 40

19 16 15 40

35 25 20 38

3 5 7 10 12 13 15

19 20 15 40

35 25 38

19 20 38 40

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

35 20 38 40

35 40 38

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)

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)

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

T ?? TInsérer ??

T ?? Textraire??

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

Tas[i ] x

Tant que (i/2 > 0 et Tas[i/2] > x) faire

Permuter (Tas, i, i/2)

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

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

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

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]

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

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)

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]

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

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]

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)

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

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).

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.

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

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.

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‎

Chapitre iv algorithmes de tri

Education

Quelques repères - infos41.pagesperso-orange.frinfos41.pagesperso-orange.fr/SCSE/ISN/...algorithmes_presentation.pdf · Les algorithmes de tri Quelques repères Etienne Poulin pour

Plan du chapitre I. Introduction II. Rappel III. Le tri Shell IV. Le tri par fusion V. Applications

ALGORITHMES DE TRI INTERNE - WordPress.com · 2017. 11. 21. · Tri interne Tri ? IFT2015 A2017 ? UdeM ? Miklos Csuros iii Tri interne : tout le ﬁchier est en memoire´ (represent´

ALGORITHMES - 3ducks.info

Algorithmes de tri - Algorithmique 1 - 2019-2020gcolas/algo-licence/slides/tris.pdfTris. 1.TrisenO(n2). I tri à bulles, I tri par insertion, I tri par sélection. 2.TrisenO(n log

New Algorithmes de tri - 1 - INFO-MPSIinfo-mpsi.weebly.com/uploads/1/3/0/1/13014682/tris.pdf · 2019. 4. 24. · Tri par comparaison On parle d’algorithme de tri par comparaison

LES ALGORITHMES DE TRI - … · CHAPITRE 3 LES ALGORITHMES DE TRI I/ Introduction ... Fin Pour 2) Fin Affiche_Tab Tableau de déclaration des objets locaux Objet Type / Nature Rôle

Algorithmes d'optimisation

Algorithmes d'approximation

INF1101 Algorithmes et structures de données1 Cours 6 Algorithmes de tri

Algorithmes et méthodes

Les algorithmes

Algorithmes de filtrage

symbioses117 · faire le tri dans toutes les infos qui circulent. Et d'interroger par exemple aussi des procédés comme les algorithmes qui viennent renforcer nos propres croyances

Algorithmes - BnF

Plateformes algorithmes travail

Algorithmes Efficaces en Calcul Formel - hal.inria.fr · 2.3 Algorithme de Karatsuba38 2.4 Transformée de Fourier rapide40 ... IV Factorisation des polynômes 18 Factorisations sans

Algorithmes - excerpts.numilog.comexcerpts.numilog.com/books/9782100701513.pdf · Algorithmes IV Chapitre4.Minorantpourletriàbattre 63 Règles pour le tri 63 Minorant pour le tri

Modèles et algorithmes

Algorithmes Amiel-Tison