[PDF] Chapitre 4 : Les algorithmes de tri





Previous PDF Next PDF



le-tri-par-insertion.pdf

12 août 2019 L'algorithme principal du tri par insertion est un algorithme qui insère un élément dans une liste d'éléments déjà triés (par exemple ...



Algorithmes de tri

Tri par sélection. Tri par insertion. Tri fusion. Le tri rapide. Des tris avec des arbres. . . Tri par tas. Optimalité des algorithmes de tri.



Chapitre 4 : Les algorithmes de tri

8.3 - Tri par insertion. • Principe de l'algorithme : – pour i 2 à n faire déplacer T[i] vers le début du tableau jusqu'à la position j<=i telle que.



Algorithmes de tri - Algorithmique 1

Arbre de décision : tri par insertion. ? Complexité des tris par comparaison dans le pire des cas : borne minimale. ? Tri rapide. ? Tri par dénombrement 



Les algorithmes de tris

Quelques algorithmes de tris. Tris élémentaires. Tri par insertion. Tri par sélection. Tri par permutation. Tris avancés. Tri Fusion. Tri rapide. Blin Lélia.



Tri par insertion Tri par fusion

ALGORITHMES DE TRI Principe : on trie récursivement le cdr de la liste puis on y insère le car ... (define tri-insertion ; ? liste de nombres triée.



TP 7 Algorithmes de tri

particulier les algorithmes de tri par insertion et tri à bulles déjà vus en première année puis l'algorithme de tri rapide (quicksort). 1 Tri à bulles.



Algorithmique Trier et Trouver

Tableaux triés algorithmes de tris. 12 de 47. Tri par insertion. Algorithme (InsertSort). Entrée : Tableau T de taille taille. Effet : T trié.



Chapitre 1 : Les algorithmes de tris par insertion et par sélection I

Spécification d'un algorithme de tri. Entrée/Sortie : tableau T (de taille n constitué d'entiers). Rôle : trier T par ordre croissant.



1 Tri par sélection

allons observer différents algorithmes de tri et surtout comparer leurs Il consiste à insérer successivement chaque élément T[i] dans la portion du ...

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 1Chapitre 3 : Les

algorithmes de tri

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 28.1 - Introduction

•Un tableau T est dit " trié en ordre croissant » si tous les éléments consécutifs du tableau vérifient :

T[i-1] £ T[i]

•Il est admis qu'un -tableau vide est trié -tableau ne contenant qu'un seul élément est trié

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 38.1 - Introduction

•D'où la définition : -Un tableau vide (n=0) est ordonné (trié), -Un tableau contenant un seul élément (n=1) est ordonné, -Un tableau T[1..n], n>1, est ordonné si " i Î [2..n], T[i-1] £ T[i]

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 48.1 - Introduction

•Tri d'un tableau -Soit un vecteur (tableau à une dimension)

T[1..n] à valeurs dans un ensemble E de

valeurs muni d'une relation d'ordre notée < -Trier le vecteur T consiste à construire un vecteur T'[1..n] tel que : •T' soit trié, •T' et T contiennent les mêmes éléments. -Le plus souvent T et T' sont le même vecteur ; T' est construit en permutant entre eux les éléments de T .

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 58.2 - Tri par

remplacement•Cette méthode simple et intuitive est malheureusement très peu performante. •Elle consiste à construire un tableau Ttrié[1..n] à partir de T[1..n] tel que :

Ttrié[i1] £ Ttrié[i] , " i Î [2..n]

•Principe : - Identifier le maximum du tableau -Rechercher le minimum du tableau T -Recopier ce minimum dans Ttri

é à la position i

-Remplacer le minimum du tableau T par le maximum -Recommencer pour i+1

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 68.2 - Tri par remplacement

Procédure tri_remplacement (D/R T[1..n], R Ttrié[1..n] : tableau de ...)

Entier i,j

E max D

ébut max A maximum(T[1..n])

i A 1 tant que ié[i] A T[j]

T[j] A max

i A i+1 ftq Ttri

é[n] A max

FinFonction maximum( D T[1..n] : tableau de ...):E

Entier i

E max D

ébut max A T[1]

Pour i A 2

à n faire

si T[i]>max alors max A T[i] fsi fpour

Retour max

Fin

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 78.2 - Tri par

remplacement •Pour chaque élément rangé dans le tableau Ttrié, il faut parcourir tout le tableau T et non une partie du tableau T •Nécessite un 2ème tableau, or si le nombre d'éléments à trier est important, cet algorithme requiert donc un espace mémoire double.

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 88.3 - Tri par insertion

•Cette méthode de tri insère (au ième passage) le ième élément T[i] à la bonne place parmi T[1],T[2]...T[i-1]. •Après l'étape i, tous les éléments entre la première et la ième position sont triés. •Il existe plusieurs méthode de tri par insertion selon le principe qui est utilisé pour rechercher le rang de l'élément à insérer parmi les éléments du début de la liste déjà triés

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 98.3 - Tri par insertion

•Principe de l'algorithme : -pour i A 2 à n faire déplacer T[i] vers le début du tableau jusqu'à la position j<=i telle que T[j] < T[k] pour j<=k=T[j-1] ou bien j=1).ki01Rang de T[i] temp

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 108.3 - Tri par insertion

Les cellules 1 à 5 sont

triées54320Les cellules 1 à 4 sont triées35420Les cellules 1 à 3 sont triées35420Les cellules 1 à 2 sont triées35042Vecteur de départ35024

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 118.3 - Tri par insertion

Procédure tri_insertion (D/R T[1..n], : tableau de ...)

Entier i,j

D

ébut pour iA 2

à n faire

j A i1 tant que j ³ 1 et T[j] > T[j+1] faire change(T,,j+1,,j)é j A j1 ftq fpour Fin

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 128.4 - Tri par sélection

•Le principe du tri par sélection d'un vecteur est d'aller chercher le plus petit élément du vecteur pour le mettre en premier, puis de repartir du second, d'aller chercher le plus petit élément pour le mettre en second etc. •Au ième passage, on sélectionne l'élément ayant la plus petite valeur parmi les positions i..n et on l'échange avec T[i].

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 138.4 - Tri par sélection

Les 4 plus petits éléments sont à

leur place54320Les 3 plus petits éléments sont à leur place45320Les 2 plus petits éléments sont à leur place35420Le plus petit élément est à sa place35420Vecteur de départ35024

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 148.4 - Tri par sélection

Procédure tri_sélection (D/R T[1..n], : tableau de ...)

Entier i,j

D

ébut pour iA 1

à n faire

pour jA i+1

à n faire

si T[i] > T[j] alors change(T,i,j)é fsi fpour fpour Fin

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 158.5 - Tri à bulles

•Le principe du tri à bulles (bubble sort) est de comparer deux à deux les éléments e1 et e2 consécutifs d'un tableau et d'effecteur une permutation si e1 > e2 . •On continue de trier jusqu'à ce qu'il n'y ait plus de permutation.

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 168.5 - Tri à bulles

Fin du deuxième et dernier

passage54320Fin du premier passage53204Vecteur de départ35024

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 178.5 - Tri à bulles

Procédure tri_bulles (D/R T[1..n], : tableau de ...)

Entier i,j

D

ébut pour iA 1

à n1 faire

pour jA n

à i+1 faire {décroissant}

si T[j1] > T[j] alors change(T,j1,j)é fsi fpour fpour Fin

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 188.5 - Tri à bulles

•Évaluation du coût de l'algorithme -Les comparaisons sont effectuées à l'intérieur de la boucle la plus interne -Pour i=1, n-1 comparaisons sont effectuées -Pour i=2, n-2 comparaisons sont effectuées -Pour i=n-1, 1 comparaison est effectuée -Le nombre total de comparaisons effectuées est donc :2 )1(1 1 nnkn k

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 198.5 - Tri à bulles

•Optimisation de l'algorithme (si temps suffisant) -Après avoir traité i-1 éléments (1 £ i £ n) •Les éléments de 1..i-1 sont triés •Tous les éléments compris entre 1..i-1 sont inférieurs aux éléments compris entre i..n

T[1..i-1] £ T[i..n]

•Les éléments compris entre i..n ne sont pas traités -Si les éléments compris entre i..n sont triés à la suite des permutations effectuées, il est inutile de poursuivre car : •T[1..i-1] trié ; T[1..i-1] £ T[i..n] ; T[i..n] trié Þ T[1..n] trié -Exemple de BATEAUX

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 20Procédure tri_bulles2 (D/R T[1..n], : tableau de ...)

Entier i,j

Bool

éen onapermutéD

ébut iA 1

onapermut

é A VRAI

Tant que onapermut

é faire

onapermut

é A FAUX

pour jA n

à i+1 faire {décroissant}

si T[j1] > T[j] alors change(T,j1,j)é onapermut

é A VRAI

fsi fpour iA i+1 ftq Fin

DEUG MIAS 1ère année -

2001/2002 Ph. Hunel - JN Provost -

V Pagé 21PRODECURE Tri_bulle (D/R T[1..n], : tableau de ...)

Booleen permut

Début REPETER

permut A FAUX

POUR i A 1

à N1 FAIRE SI T[i] > T[i+1] ALORS

change(T,i,i+1)é permut A VRAI FSi Fpour

Jusqu'

à permut = FAUXFIN

quotesdbs_dbs20.pdfusesText_26