Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Expose tri bulles 1 C O U - UDLA ENSETDLA GPI R S TRI À BULLES ET COMPLEXITÉ D E C MASTER I ?? GPI O M Étudiants P L NANGA GWOGON Thomas E X NDONGO ATEBA Christine Michelle I NGOG MOMNOUGUI Paul Valery T E D E ENSEIGNANT S A Mr NGUEJIEP Jean Baptiste L In

C O U - UDLA ENSETDLA GPI R S TRI À BULLES ET COMPLEXITÉ D E C MASTER I ?? GPI O M Étudiants P L NANGA GWOGON Thomas E X NDONGO ATEBA Christine Michelle I NGOG MOMNOUGUI Paul Valery T E D E ENSEIGNANT S A Mr NGUEJIEP Jean Baptiste L Ingénieur en Génie Logiciel G O R I T H M E S EXPOSE SUR L ? ALGORITHME DU TRI À BULLES BUBBLE SORT CTABLE DE MATIERE INTRODUCTION I PRINCIPE DU TRI A BULLES a Principe b Présentation c Variantes d Exemple d ? application II COMPLEXITÉ DU TRI BULLE a Algorithme b Complexité c Notation de LANDAU III CONCLUSION IV BIBLIOGRAPHIE WEBOGRAPHIE CINTRODUCTION 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 CI PRINCIPE DU TRI BULLE a Principe Le principe du tri bulle bubble sort ou sinking sort est de comparer deux à deux les éléments a et a consécutifs d ? un tableau et d ? e ?ecteur une permutation si a a 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 e ?ectuée Ensuite sont comparés et éventuellement permutés les valeurs et et jusqu ? à n- 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- é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 e ?ectuer 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 ?n 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 La suite a a 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