Introduction à l'algorithmique 12 - Le tri à bulles

Bonjour à tous ! Aujourd'hui nous allons aborder notre premier algorithme de tri ! Grâce à cet algorithme nous allons revoir les notions suivantes : Les structures conditionnelles, les boucles, les tableaux et les fonctions. C'est un bon exercice !

Tout d'abord, un algorithme de tri permet de trier une structure de données (ici un tableau). Le tri à bulles et l'un des algorithmes de tri les plus connu, son principe est simple.

• L'algorithme parcourt le tableau et compare des pairs de valeurs. (tab[0] et tab[1], puis tab[1] et tab[2]...)
• Lorsque deux éléments successifs ne sont pas dans l'ordre, on les échanges.
• Après chaque parcours complet du tableau, l'algorithme vérifie si des variables ont été échangées. Si oui, alors l'algorithme refait un parcours entier. Si non, alors ça veut dire que le tableau est trié. Je vous propose une petite vidéo et un schéma qui illustrerons mieux ce principe (vous pouvez couper le son... )

Vous devez avoir une vague idée de la manière dont on va s'y prendre pour le faire, n'est-ce pas ? Aller, on se lance !

Pseudo-code du module principal :

DÉBUT
  atrier <- [6, 5, 1, 2, 8, 9, 3, 7, 4]
  ECRIRE "Voici le tableau a trier: ", atrier
  ECRIRE "Voici le tableau trié:", TRI_A_BULLES(atrier)
FIN

Pseudo-code du module TRI_A_BULLES

ENTRER tab
  echange <- 1
  TANTQUE echange = 1 FAIRE
    echange <- 0
    POUR compteur = 1 JUSQU'À COMPTER(tab) - 1 FAIRE
      SI tab[compteur] > tab[compteur + 1] ALORS
        tmp <- tab[compteur + 1]
        tab[compteur + 1] <- tab[compteur]
        tab[compteur] <- tmp
        echange <- 1
      FINSI
    FINPOUR
  FINTANTQUE
RETOURNER tab

L'algorithme du tri à bulles est l'un des premiers vrais algorithmes que vous apprendrez en cours de programmation. Toutefois sa complexité informatique est élevée. Nous verrons ce que cela signifie... demain !