Algorithmes de tri

Tri par bulles

Le tri par bulles procède comme suit:

Mise en application du tri par bulles sur une liste d'entiers

Cette méthode de tri consiste à traverser plusieurs fois la liste de gauche à droite en échangeant à chaque passage des éléments adjacents placés dans un mauvais ordre relatif. Plus précisément, dès que l'élément de plus grande valeur est rencontré lors de la première traversée, il est échangé avec chacun des éléments situés à sa droite jusqu'à ce qu'il trouve sa place définitive, à l'extrémité droite de la liste. A la deuxième traversée, c'est l'élément ayant la deuxième plus grande valeur qui est successivement poussé vers sa place définitive et ainsi de suite, comme l'illustre la figure ci-dessous:

algo3.jpg

Déroulement du tri par bulles sur une liste d'entiers

Chaque traversée permet de placer un élément à sa place définitive en commençant par celui ayant la plus grande valeur. Dès lors, les éléments situés à droite de l'indice i sont à leur position définitive.

A vous de jouer !

En vous basant sur les exemples présentés ci-dessus, répondez à chacun des points suivants:

  1. Appliquez le tri par bulles sur les 9 cartes d'une même famille de cartes.
  2. Décrivez chacune des étapes de progression du tri par bulles appliqué à la liste [91, 17, 2, 35, 54]. Au besoin, recourez au programme TestBulles vous permettant de valider votre réponse.
  3. Pour chacune des listes suivantes, calculez le nombre de comparaisons et le nombre de déplacements d'éléments nécessaires à son tri puis généralisez vos résultats pour des listes similaires comportant 10, 100 puis n éléments. Au besoin, recourez au programme AnalyseComplexite vous permettant de valider vos réponses.
    1. croissante = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    2. decroissante = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    3. aleatoire = [54, 26, 93, 31, 77, 17, 44, 55, 20, 36]
  4. Implémentez le tri par bulles en Python en vous basant sur le squelette téléchargeable ici.

|