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)FINPseudo-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 FINTANTQUERETOURNER tabL'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 !