2017-2018 UDLA/ ENSETDLA/GPI4 EXPOSE SUR L’ALGORITHME DU TRI À BULLES (BUBBLE S

2017-2018 UDLA/ ENSETDLA/GPI4 EXPOSE SUR L’ALGORITHME DU TRI À BULLES (BUBBLE SORT). MASTER I – GPI Étudiants NANGA GWOGON Thomas NDONGO ATEBA Christine Michelle NGOG MOMNOUGUI Paul Valery TRI À BULLES ET COMPLEXITÉ ENSEIGNANT Mr NGUEJIEP Jean Baptiste Ingénieur en Génie Logiciel C O U R S D E C O M P L E X I T E D E S A L G O R I T H M E S TABLE DE MATIERE INTRODUCTION .................................................................................................................... 1 I. PRINCIPE DU TRI A BULLES ......................................................................................... 2 a. Principe ........................................................................................................................... 2 b. Présentation ..................................................................................................................... 2 c. Variantes ......................................................................................................................... 3 d. Exemple d’application .................................................................................................... 4 II. COMPLEXITÉ DU TRI BULLE ...................................................................................... 5 a. Algorithme ...................................................................................................................... 5 b. Complexité ...................................................................................................................... 8 c. Notation de LANDAU .................................................................................................... 6 III. CONCLUSION .................................................................................................................. 7 IV. BIBLIOGRAPHIE/WEBOGRAPHIE ............................................................................ 8 1 INTRODUCTION Dans le cadre du cours d’algorithmes et complexités dispensé à l’École Normale Supérieure d’Enseignement Technique (ENSET) de l’université de Douala, le présent document rédigé par les étudiants de Master I Gestion de Projets informatiques (GPI) dudit établissement, a pour but de présenter de manière précise et concise ce qu’est l’algorithme du tri à bulles. Pour ce faire il est énoncé ici, le principe de ce tri, ainsi que le calcul de sa complexité dans le pire des cas et la déduction de la notation de LANDAU correspondante. 2 I. PRINCIPE DU TRI BULLE a. Principe Le principe du tri bulle (bubble sort ou sinking sort) est de comparer deux à deux les éléments a1 et a2 consécutifs d’un tableau et d’effecteur une permutation si a1 > a2 en comparant chaque case à la suivante. On continue de trier jusqu’à ce qu’il n’y ait plus de permutation. b. Présentation L’algorithme du tri bulle se déroule comme suit : les deux premiers éléments du tableau sont comparés, si le premier élément est supérieur au second, une permutation est effectuée. Ensuite, sont comparés et éventuellement permutés les valeurs 2 et 3, 3 et 4 jusqu’à (n-1) et n passages (n représentant le nombre de valeurs à trier). Une fois cette étape achevée, il est certain que le dernier élément du tableau est le plus grand. L’algorithme reprend donc pour classer les (n-1) éléments qui précédent. Il se termine quand il n’y a plus de permutations possibles. Pour classer les n valeurs du tableau, il faut, au pire, effectuer l’algorithme n fois. Avec de la logique, on s’aperçoit qu’au premier passage, on place le plus grand élément de la liste à la fin du tableau, au bon emplacement. Pour le passage suivant, nous ne sommes donc plus obligés de faire une comparaison avec le dernier élément ; et c’est bien plus avantageux ainsi. De ce fait, à chaque passage, le nombre de valeurs à comparer diminue de 1. La suite (a1, a2 ..., an) est rangée dans un tableau T [...] en mémoire centrale. Le tableau contient une partie triée (en violet à droite) et une partie non triée (en blanc à gauche). On effectue plusieurs fois le parcours du tableau à trier; le principe de base étant de réordonner les couples (ai-1, ai) non classés (en inversion de rang soit ai-1 > ai) dans la partie non triée du tableau, puis à déplacer la frontière (le maximum de la sous-suite (a1, a2 ..., an-1)) d’une position comme le montre la figure ci-dessous: 3 Tant que la partie non triée n’est pas vide, on permute les couples non ordonnés ((ai-1, ai) tels que ai-1 > ai)) pour obtenir le maximum de celle-ci à l’élément frontière. C’est-à-dire qu’au premier passage c’est l’extremum global qui est bien classé, au second passage le second extremum, etc. c. Variantes Cet algorithme porte le nom de tri bulle, car, petit à petit, les plus grands éléments du tableau remontent, par le jeu des permutations, en fin de tableau. Dans un aquarium il en va de même : les plus grosses bulles remontent plus rapidement à la surface que les petites qui restent collées au fond. Il existe plusieurs variantes de cet algorithme : - La première consiste à n’effectuer les comparaisons que sur les éléments du tableau qui ne sont pas remontés à la surface (triés). Ainsi, si n est le nombre d’éléments du tableau et i le nombre de fois où le parcours complet du tableau a été effectué, à chaque itération, seuls les (n-i) premiers éléments sont comparés. Le gain de temps apporté par cette optimisation est d’ailleurs loin d’être négligeable, c’est pourquoi une version de ce tri bulle optimisé est également présentée. - Une autre variante du tri bulle, qui n’est pas très différente, consiste à faire descendre les plus petites valeurs au début du tableau. Dans ce cas, le tableau est parcouru, non plus de gauche à droite, mais de droite à gauche. Dans sa version optimisée, ce sont les (n-i) derniers éléments qui sont comparés. Cette variante est utilisée pour implémenter le tri bulle dans le cas de listes ou de piles. - La seconde consiste à reprendre au début chaque fois qu’une permutation est détectée. Ainsi, les plus petits et les plus grands éléments vont tout doucement migrer en début et en fin de tableau. Cette version de l’algorithme est aussi connue sous le nom de "tri Shaker" ou de "tri Shuttle". - Une autre version est le "tri bidirectionnel". Elle consiste à parcourir le tableau de gauche à droite, puis de droite à gauche, le changement de direction ayant lieu chaque fois que l’une des extrémités est atteinte. Ainsi, les plus petits éléments du tableau descendent au même rythme que remontent les plus gros éléments. 4 d. Exemple d’application du tri bulle un tableau de nombres Soit les éléments du tableau suivant « 5 1 4 2 8 » ; pour chaque étape, les éléments comparés sont en gras. Étape 1. 1.1. (5 1 4 2 8) => (1 5 4 2 8). Les nombres 5 et 1 sont comparés, et comme 5 > 1, l’algorithme les échange. 1.2. (1 5 4 2 8) => (1 4 5 2 8).Échange, car 5>4. 1.3. (1 4 5 2 8) => (1 4 2 5 8).Échange, car 5>2. 1.4. (1 4 2 5 8) => (1 4 2 5 8). Pas d’échange, car 5 < 8. À la fin de cette étape, un nombre est à sa place définitive, le plus grand : 8. Étape 2. 2.1. (1 4 2 5 8) => (1 4 2 5 8). Pas d’échange. 2.2. (1 4 2 5 8) => (1 2 4 5 8). Échange. 2.3. (1 2 4 5 8) => (1 2 4 5 8). Pas d’échange. Les éléments 5 et 8 du tableau ne sont pas comparés puisqu’on sait que le 8 est déjà à sa place définitive. Par hasard, tous les nombres sont déjà triés, mais cela n’est pas encore détecté par l’algorithme. Étape 3. 3.1. (1 2 4 5 8) => (1 2 4 5 8). Pas d’échange. 3.2. (1 2 4 5 8) => (1 2 4 5 8). Pas d’échange. Les deux derniers nombres sont exclus des comparaisons, puisqu’on sait qu’ils sont déjà à leur place définitive. Puisqu’il n’y a eu aucun échange durant cette étape 3, le tri optimisé se termine. Étape 4. 4.1. (1 2 4 5 8) => (1 2 4 5 8). Pas d’échange. Le tri est terminé, car on sait que les 4 plus grands nombres, et donc aussi le 5e, sont à leur place définitive. 5 II. COMPLEXITÉ DU TRI BULLE a. Algorithme Procédure Tri_bulle (type tableau tab [] :d’entiers ; n : entier) ; Var : i, j, aide entier Début Pour i <= 1 à n Faire Pour j <= i+1 à n Faire Si (tab[j] < tab [j-1]) Alors aide <= tab[j] tab [j] <= tab [j-1] tab [j-1] <= aide Fin_si Fin_pour Fin_pour Fin b. Complexité : coût et nombre d’exécutions dans le pire des cas Considérons la complexité, en nombre d’opérations du tri bulle, pour un tableau ou une liste de n éléments. Dans le pire des cas, ce qui correspond à un tableau préalablement trié de manière décroissante, il a des permutations jusqu’à ce que la liste ait été parcourue (n-1) fois. Début Pour i <= 1 à n Faire C1 Pour j <= i+1 à n Faire C2 Si (tab[j] < tab [j-1]) Alors aide <= tab[j] tab [j] <= tab [j-1] C3 tab [j-1] <= aide Fin_si Fin_pour Fin_pour Fin La simulation élaborée sur le coût et le nombre d’exécutions pour le pire des cas de cet algorithme a donné le résultat du temps d’exécution ci-dessous : T(n) =
   
      
∑     coût nombre d’exécutions C1 n +1 C2      C3     6 Or:
∑   =
∑    
∑      Alors : T(n) =
    

       uploads/Litterature/ expose-tri-bulles.pdf

Documents similaires

Classe de douzième - page 1 - 12e 15  Programme  15 Lecture Dans La lecture i 0 0

TEST PSYSCHOTECHNIQUE1: Test mécanique : Les tests de raisonnement mécanique so 0 0

IUT C de Roubaix DUT STID 1re Année 2011-2012 Corrigé interrogation de probabil 0 0

République Algérienne Démocratique et Populaire Ministère de l’Enseignement Sup 0 0

Fiche pédagogique : 1 Classe de deuxième année baccalauréat Lettres Activité de 0 0

1 Economie –TP informatique série théorique -2019/2020 – partie1 Tableur 4 eco 0 0

Binaire et hexadécimal Ici, je vous apprendrais ce qu'il faut savoir à propos d 0 0

Raccourcis clavier Microsoft Word Fichier à Alt + F Fichier à Nouveau à Ctrl + 0 0

Comparaison entre un automate et un arbre Introduction On va dans cet exposé co 0 0

[1] Kevin Quinn Avery, The numbers of life, DoubleDay, (1977). Les dossiers de 0 0

• Détails
• Publié le Jul 14, 2022
• Catégorie Literature / Litté...
• Langue French
• Taille du fichier 0.2340MB