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... )
tri à bulle

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 TRIABULLES

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  FINTANTQUERETOURNER 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 !