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

INF1101 Algorithmes et structures de données

1

Cours 6Cours 6

Algorithmes de triAlgorithmes de tri


2

Plan du cours 6Plan du cours 6

I.I. Notions de base Notions de baseII.II. Les tris simplesLes tris simplesIII.III. Mergesort MergesortIV.IV. Quicksort Quicksort


3

I – Notions de base:I – Notions de base:l’utilité des trisl’utilité des trisProblématique:Problématique:

• Un grand nombre de problèmes réels ont recours à Un grand nombre de problèmes réels ont recours à la recherche d’éléments dans un vecteur (tableau). la recherche d’éléments dans un vecteur (tableau). Cette recherche devient quasiment impossible Cette recherche devient quasiment impossible lorsqu’elle s’effectue dans un vecteur désordonné, lorsqu’elle s’effectue dans un vecteur désordonné, d’où le besoin de trier les vecteurs avant d’y d’où le besoin de trier les vecteurs avant d’y effectuer un traitement.effectuer un traitement.

Exemples:Exemples:• Les mots dans un dictionnaire.Les mots dans un dictionnaire.• Fichiers dans un répertoire de PC.Fichiers dans un répertoire de PC.• Les CD répertoriés dans un magasin de musique.Les CD répertoriés dans un magasin de musique.• Les sigles des cours de Poly offert pour une session.Les sigles des cours de Poly offert pour une session.


4

DéfinitionsDéfinitions

• Tri interneTri interne : se dit d'un algorithme : se dit d'un algorithme qui n'utilise pas de tableau qui n'utilise pas de tableau temporaire pour effectuer le tri.temporaire pour effectuer le tri.

• Tri externeTri externe : se dit d'un algorithme : se dit d'un algorithme de tri qui nécessite l'utilisation d'un de tri qui nécessite l'utilisation d'un tableau temporaire.tableau temporaire.


5

II – Les tris simplesII – Les tris simples

• Tri par sélection Tri par sélection • Tri en bulleTri en bulle• Tri par insertionTri par insertion


6

Tri par sélectionTri par sélection

• IdéeIdée : Cette technique consiste à : Cette technique consiste à parcourir séquentiellement le parcourir séquentiellement le vecteur à trier. À l'itération vecteur à trier. À l'itération ii, la plus , la plus petite valeur du tableau est petite valeur du tableau est interchangée avec la valeur située interchangée avec la valeur située dans la case d'indice dans la case d'indice ii..


7

[1][1][2][2][4][4][3][3][4][4]

Exemple d’exécution du tri Exemple d’exécution du tri par sélectionpar sélection

771010

22

1515

88

0 1 2 3 40 1 2 3 4 ii

min min = =

[0][0]

i =i = 00112233


8

Programmation du tri par Programmation du tri par sélectionsélectiontemplate<class T>template<class T>void TriSelection( vector<T>& Tableau, int n)void TriSelection( vector<T>& Tableau, int n){ { int i, j, min;int i, j, min; T Tmp;T Tmp; for ( i=0 ; i<n-1 ; i++ ) {for ( i=0 ; i<n-1 ; i++ ) {

//Identification de l'index du plus petit element//Identification de l'index du plus petit element min = i;min = i; for ( j=i+1 ; j<n ; j++ ) { for ( j=i+1 ; j<n ; j++ ) { if ( Tableau[j]<Tableau[min] )if ( Tableau[j]<Tableau[min] ) min = j;min = j; }} //Permutation des elements//Permutation des elements Tmp = Tableau[i];Tmp = Tableau[i]; Tableau[i]Tableau[i] == Tableau[min];Tableau[min]; Tableau[min]Tableau[min] == Tmp;Tmp;

}}}}


9

Tri en bulleTri en bulle

• IdéeIdée : Les petits éléments du tableau : Les petits éléments du tableau « remontent » (comme des bulles) « remontent » (comme des bulles) vers le début du tableau pour vers le début du tableau pour atteindre leur position finale. Les plus atteindre leur position finale. Les plus « légers » remontent le plus « légers » remontent le plus rapidement. Une fois tous les rapidement. Une fois tous les éléments remontés, le tableau est éléments remontés, le tableau est trié.trié.


10

Exemple d’exécution du tri Exemple d’exécution du tri en bulleen bulle

771010

22

1515

88

0 1 2 3 40 1 2 3 4 ii

: comparaison de: comparaison de deux élémentsdeux éléments

Position de iPosition de i


11

Programmation du tri en Programmation du tri en bullebulle

template<class T>template<class T>void TriBulle(void TriBulle(vector<T>& Tableauvector<T>& Tableau, int n), int n){ {

int i,j;int i,j;T Tmp;T Tmp;for ( i=0; i<n-1; i++)for ( i=0; i<n-1; i++)

for ( j=n-1; j>i; j--)for ( j=n-1; j>i; j--)if ( Tableau[j-1]> Tableau[j])if ( Tableau[j-1]> Tableau[j]){ {

Tmp = Tableau[j-1];Tmp = Tableau[j-1];Tableau[j-1] = Tableau[j];Tableau[j-1] = Tableau[j];Tableau[j] = Tmp;Tableau[j] = Tmp;

}}}}


12

Tri par insertionTri par insertion

• IdéeIdée : Cette stratégie est semblable : Cette stratégie est semblable à la méthode qu'utilise naturellement à la méthode qu'utilise naturellement un joueur de cartes pour organiser sa un joueur de cartes pour organiser sa main. À chaque étape, une partie du main. À chaque étape, une partie du tableau est déjà ordonnée et une tableau est déjà ordonnée et une nouvelle valeur est insérée à nouvelle valeur est insérée à l'endroit approprié.l'endroit approprié.


13

Exemple d’exécution par Exemple d’exécution par insertioninsertion

771010

22

1515

88

0 1 2 3 40 1 2 3 4 ii


14

Programmation du tri par Programmation du tri par insertioninsertion

template < class T>template < class T>void TriInsertion(vector<T>& Tableau, int n)void TriInsertion(vector<T>& Tableau, int n){{

int i,j;int i,j;T Tmp;T Tmp;for ( i=1;i<n; i++ )for ( i=1;i<n; i++ ){ {

//Placer l'element courant dans la variable tampon//Placer l'element courant dans la variable tamponTmp = Tableau[i];Tmp = Tableau[i];j=i;j=i;

//Tant que la position d'insertion n'est pas atteinte...//Tant que la position d'insertion n'est pas atteinte...while ( (--j>=0) && (Tmp<Tableau[j]) )while ( (--j>=0) && (Tmp<Tableau[j]) )Tableau[j+1]=Tableau[j];Tableau[j+1]=Tableau[j];

Tableau[j+1]=Tmp;Tableau[j+1]=Tmp;}}

}}


15

Analyse des tris simplesAnalyse des tris simples

• Meilleur cas: tableau déjà triéMeilleur cas: tableau déjà trié

• Cas moyen: tableau aléatoireCas moyen: tableau aléatoire

• Pire cas: tableau trié à l’enversPire cas: tableau trié à l’envers

1 3 5 7 9 10

13

18

21

25

7 10

21

9 1 25

18

3 5 13

25

21

18

13

10

9 7 5 3 1


16

Comparaison des tris Comparaison des tris simplessimples

Pire cas Cas moyen Meilleur cas

Tri par sélectionTri en bulle

Tri par insertion

2nO 2nO 2nO 2nO 2nO 2nO 2nO nO

2nO


17

III – Le mergesortIII – Le mergesortProblématique :Problématique :• Le tri est effectué en utilisant la technique de Le tri est effectué en utilisant la technique de

diviser-et-conquérirdiviser-et-conquérir, en divisant le problème en , en divisant le problème en deux sous-problèmes de complexité résolus deux sous-problèmes de complexité résolus récursivement, offrant une complexité globale de récursivement, offrant une complexité globale de

• L'algorithme de tri Mergesort :L'algorithme de tri Mergesort :1.1.Si le nombre d’éléments à trier == (0 ou 1), retourner.Si le nombre d’éléments à trier == (0 ou 1), retourner.2.2.Trier récursivement la première et deuxième moitié Trier récursivement la première et deuxième moitié

séparément.séparément.3.3.Regrouper les deux parties triées dans un nouveau Regrouper les deux parties triées dans un nouveau

groupe trié.groupe trié.

n nn 2log


18

MergeSortMergeSort

Actr Bctr

Cctr

1 13 24 26 2 15 27 381 213 1524 26 27 38


19

La fonction MergesortLa fonction Mergesort// Routine interne : Tableau: le vecteur d’éléments// Routine interne : Tableau: le vecteur d’éléments// tmpTab: vecteur temporaire pour les résultats// tmpTab: vecteur temporaire pour les résultats// left, right: indices gauche et droit des tableaux// left, right: indices gauche et droit des tableauxtemplate <class T> template <class T> void mergeSort(vector<T>& Tableau, vector<T>& tmpTab,void mergeSort(vector<T>& Tableau, vector<T>& tmpTab, int left, int right)int left, int right){{ if (left < right)if (left < right) {{ int center = (left+right)/2;int center = (left+right)/2; mergeSort(Tableau, tmpTab, left, center)mergeSort(Tableau, tmpTab, left, center) mergeSort(Tableau, tmpTab, center+1, right);mergeSort(Tableau, tmpTab, center+1, right); merge(Tableau, tmpTab, left, center+1, right);merge(Tableau, tmpTab, left, center+1, right); }}}}template <class T> template <class T> // Fonction principale// Fonction principalevoid mergeSort(vector<T>& Tableau)void mergeSort(vector<T>& Tableau){{ vector<T> tmpTab(Tableau.size());vector<T> tmpTab(Tableau.size()); mergeSort(Tableau,tmpTab,0,Tableau.size()-1);mergeSort(Tableau,tmpTab,0,Tableau.size()-1);}}


20

La fonction MergeLa fonction Merge// Routine interne : Tableau: le vecteur d’éléments// Routine interne : Tableau: le vecteur d’éléments//// tmpTab: vecteur pour les résultats du merge tmpTab: vecteur pour les résultats du merge//// leftPos: indice gauche du tableau leftPos: indice gauche du tableau//// rightPos: indice du début de la 2ieme demi rightPos: indice du début de la 2ieme demi//// rightEnd: indice droit du tableau rightEnd: indice droit du tableautemplate <class T> template <class T> void merge(vector<T>& Tableau, vector<T>& tmpTab, int leftPos, void merge(vector<T>& Tableau, vector<T>& tmpTab, int leftPos, intint rightPos, int rightEnd)rightPos, int rightEnd){{ int leftEnd = rightPos-1;int leftEnd = rightPos-1; int tmpPos = leftPos;int tmpPos = leftPos; int numElements = rightEnd – leftPos +1;int numElements = rightEnd – leftPos +1;

//Boucle principale//Boucle principale while( leftPos<=leftEnd && rightPos<=rightEnd)while( leftPos<=leftEnd && rightPos<=rightEnd) if(Tableau[leftPos]<Tableau[rightPos])if(Tableau[leftPos]<Tableau[rightPos]) tmpTab[tmpPos++]=Tableau[leftPos++];tmpTab[tmpPos++]=Tableau[leftPos++]; elseelse tmpTab[tmpPos++]=Tableau[rightPos++];tmpTab[tmpPos++]=Tableau[rightPos++]; . . . (suite). . . (suite)


21

La fonction MergeLa fonction Merge

. . .. . .

while(leftPos<=leftEnd) while(leftPos<=leftEnd) // Copie le reste de la 1ere demie// Copie le reste de la 1ere demie tmpTab[tmpPos++]=Tableau[leftPos++];tmpTab[tmpPos++]=Tableau[leftPos++];

while(rightPos<=rightEnd) while(rightPos<=rightEnd) // Copie le reste de la 2ieme demie// Copie le reste de la 2ieme demie tmpTab[tmpPos++]=Tableau[rightPos++];tmpTab[tmpPos++]=Tableau[rightPos++];

// Copie tmpTableau dans Tableau// Copie tmpTableau dans Tableau for( int i=0; i<numElements ; i++, rightEnd--)for( int i=0; i<numElements ; i++, rightEnd--) Tableau[rightEnd]=tmpTab[rightEnd];Tableau[rightEnd]=tmpTab[rightEnd];}}


22

IV - Le tri rapide IV - Le tri rapide (Quicksort)(Quicksort)

Problématique :Problématique :• Le tri est une tâche importante en Le tri est une tâche importante en

programmation. Il est donc essentiel que programmation. Il est donc essentiel que celui-ci soit effectué avec efficacité et celui-ci soit effectué avec efficacité et rapidité.rapidité.

• L'algorithme de tri Quicksort tente L'algorithme de tri Quicksort tente d'atteindre cet objectif par l'utilisation du d'atteindre cet objectif par l'utilisation du concept de récursivité.concept de récursivité.


23

Le tri rapide (suite)Le tri rapide (suite)Idée générale :Idée générale :Dans cet algorithme, l'exécution du tri est simplement déléguée Dans cet algorithme, l'exécution du tri est simplement déléguée à une série d'appels récursifs. Une fonction de à une série d'appels récursifs. Une fonction de partitionnementpartitionnement est d'abord appelée. Cette fonction choisit arbitrairement un est d'abord appelée. Cette fonction choisit arbitrairement un pivotpivot qui est utilisé pour subdiviser le tableau en deux parties: qui est utilisé pour subdiviser le tableau en deux parties:

1.1. une partie de gauche où tous les éléments ont une valeur plus une partie de gauche où tous les éléments ont une valeur plus petite ou égale au pivot;petite ou égale au pivot;

2.2. une partie de droite où tous les éléments ont une valeur plus une partie de droite où tous les éléments ont une valeur plus grande ou égale au pivot.grande ou égale au pivot.

Par la suite, les deux parties ainsi obtenues sont triées par deux Par la suite, les deux parties ainsi obtenues sont triées par deux appels récursifs à la fonction de tri rapide.appels récursifs à la fonction de tri rapide.

En plus de la fonction principale de tri rapide, une autre fonction En plus de la fonction principale de tri rapide, une autre fonction est donc requise: celle qui procède à la partition du tableau.est donc requise: celle qui procède à la partition du tableau.


24

La fonction QuicksortLa fonction Quicksort

template <class T>template <class T>void QuickSort(vector<T>& tableau, int inf, int sup)void QuickSort(vector<T>& tableau, int inf, int sup){{

int milieu;int milieu;if (sup>inf)if (sup>inf) // s'il y a au moins 2 éléments// s'il y a au moins 2 éléments{{

milieu = Partition(tableau,milieu = Partition(tableau, inf,inf, sup);sup);

// trier la partie de gauche// trier la partie de gaucheQuickSort(tableau,QuickSort(tableau, inf,inf, milieu);milieu);// trier la partie de droite// trier la partie de droiteQuickSort(tableau,QuickSort(tableau, milieu+1, sup);milieu+1, sup);

}}}}


25

Exemple d’exécution de Exemple d’exécution de PartitionPartition

771111

22

9955

0 1 2 3 40 1 2 3 4 ii

ii jj

Pivot = Tab[2] = 5 Pivot = Tab[2] = 5 Premier appelPremier appelQuicksort(a,0,4)Quicksort(a,0,4)


26

La fonction PartitionLa fonction Partition

template <class T>template <class T>int Partition(vector<T>& tableau, int inf, int sup)int Partition(vector<T>& tableau, int inf, int sup){{

T pivot, tempo;T pivot, tempo;int i,j;int i,j;pivot = tableau[(sup+inf)/2];pivot = tableau[(sup+inf)/2];i = inf-1;i = inf-1;j = sup+1;j = sup+1;

// Suite a la page suivante// Suite a la page suivante


27

La fonction Partition (suite)La fonction Partition (suite)

while ( i<j ) while ( i<j ) // tant que les index ne croisent pas// tant que les index ne croisent pas { { // conserver les éléments plus petits ou égaux // conserver les éléments plus petits ou égaux //au pivot à sa gauche//au pivot à sa gauche dodo { i++;{ i++; } while (tableau[i]<pivot);} while (tableau[i]<pivot); // conserver les éléments plus grands ou // conserver les éléments plus grands ou //égaux au pivot à sa droite//égaux au pivot à sa droite do do { j--;{ j--; } while (tableau[j]>pivot);} while (tableau[j]>pivot); // Permuter les éléments qui ne sont pas// Permuter les éléments qui ne sont pas // à leur place// à leur place if ( i<j)if ( i<j) {{ tempo = tableau[i];tempo = tableau[i];

tableau[i]= tableau[j];tableau[i]= tableau[j];tableau[j]= tempo;tableau[j]= tempo;

}} }}

return j; }return j; }


28

Complexité du QuicksortComplexité du Quicksort

Cas moyen et meilleur casCas moyen et meilleur cas• Complexité du Quicksort dans le cas Complexité du Quicksort dans le cas

moyen et dans le meilleur moyen et dans le meilleur cas .cas .

Pire casPire cas• Complexité du Quicksort dans le pire Complexité du Quicksort dans le pire

cas: cas:

nn 2log

2n

Documents

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