Algorithme : Tri à Bulle du tableau des entiers
Plan de tutoriel
1- Principe du tri à Bulle
2- Algorithme du tri à Bulle
3- Programme Python
Principe du tri à Bulle
Le tri à bulle est un algorithme permettant de trier les éléments d’un tableau, généralement dans l’ordre croissant. Son principe consiste à parcourir le tableau et à comparer les éléments voisins deux à deux.
Lorsqu’un élément est supérieur à l’élément qui le suit, les deux éléments sont dans le mauvais ordre. Ils sont alors échangés afin de placer le plus petit élément avant le plus grand. Cette opération est répétée pour les différents éléments du tableau.
À chaque passage, le plus grand élément de la partie non encore triée se déplace progressivement vers la fin du tableau. C’est cette progression vers la fin du tableau qui explique le nom de « tri à bulle », car les plus grandes valeurs remontent progressivement vers leur position définitive.
Après chaque passage, la dernière position concernée est considérée comme triée. Le nombre d’éléments à parcourir diminue donc progressivement. Le processus continue jusqu’à ce qu’aucun échange ne soit effectué, ce qui signifie que le tableau est déjà trié.
Par exemple, pour le tableau [5, 2, 8, 1], on compare d’abord 5 et 2. Comme 5 est supérieur à 2, les deux valeurs sont échangées et le tableau devient [2, 5, 8, 1]. Ensuite, on compare 5 et 8 : aucun échange n’est nécessaire. Enfin, 8 et 1 sont comparés et échangés, ce qui donne [2, 5, 1, 8]. À la fin de ce premier passage, la plus grande valeur, 8, est donc placée à sa position définitive.
Le même principe est ensuite appliqué aux éléments restants. Les passages successifs permettent de placer progressivement les autres valeurs dans leur position correcte. Lorsque le tableau est entièrement trié, aucun échange n’est effectué et l’algorithme s’arrête.
Algorithme du tri à Bulle
Dans cet algorithme, On va utiliser deux fonctions et trois procédures :
- la fonction saisie
- la procédure remplir
- la procédure bulle
Algorithme du programme Principal
Le programme principal constitue le point de départ de l’exécution du programme. Il organise les différentes étapes nécessaires pour saisir, remplir, trier et afficher le tableau.
Tout d’abord, l’instruction n = saisie() permet de saisir et contrôler le nombre d’éléments du tableau. Ensuite, la procédure remplir(t, n) permet de remplir le tableau avec les n valeurs saisies par l’utilisateur.
La procédure bulle(t, n) est ensuite appelée pour trier les éléments du tableau dans l’ordre croissant en utilisant l’algorithme du tri à bulle.
Enfin, le programme affiche un message indiquant que le tableau est trié, puis la procédure afficher(t, n) permet d’afficher les éléments du tableau après le tri.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Algorithme tri_bulle Debut # Saisir la taille du tableau n <-- saisie() # Afficher un message avant le remplissage Ecrire("***Remplissage du tableau***") # Remplir le tableau avec les valeurs saisies remplir(t, n) # Trier le tableau dans l'ordre croissant # en utilisant l'algorithme du tri à bulle. bulle(t, n) # Afficher un message indiquant que le tableau est trié Ecrire("***Tableau trié***") # Afficher les éléments du tableau trié afficher(t, n) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
| t | tableau des entiers |
La fonction saisie
La fonction saisie() permet de saisir et de contrôler le nombre d’éléments n du tableau. Elle demande à l’utilisateur de donner une valeur comprise entre 2 et 14.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Fonction saisie():entier # Demander à l'utilisateur de saisir le nombre d'éléments # La valeur doit être comprise entre 2 et 14. Ecrire ("donner n entre 2 et 14") Lire(n) # Vérifier que n appartient à l'intervalle [2, 14] # Tant que la valeur est incorrecte, on redemande la saisie. Tant que Non (2<=n<=14) faire Ecrire ("donner n entre 2 et 14") Lire(n) Fin tant que # Retourner la valeur correcte de n Retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La procédure remplir
La procédure remplir permet de remplir le tableau t avec n entiers saisis par l’utilisateur.
|
1 2 3 4 5 6 7 8 9 |
Procédure remplir(var t:tab; n:entier) # Parcourir les n premières cases du tableau Pour i de 0 à n-1 faire # Demander à l'utilisateur de saisir un élément # et le placer dans la case t[i]. Ecrire('Donner un élément du tableau') Lire(t[i]) Finpour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| binaire | chaîne des caractères |
La procédure bulle
La procédure bulle(t, n) permet de trier les n premiers éléments du tableau t dans l’ordre croissant en utilisant l’algorithme du tri à bulle.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
Procédure bulle(var t:tab;n:entier) # La variable permuter indique si au moins un échange # a été effectué pendant le passage. # Au départ, on considère qu'un échange est possible. permuter <-- Vrai # Répéter les passages tant qu'un échange a été effectué # et qu'il reste au moins deux éléments à comparer. Tant que (permuter = Vrai) et (n > 1) faire # Au début de chaque passage, on considère # qu'aucun échange n'a encore été effectué. permuter <-- Faux # Parcourir le tableau en comparant les éléments # voisins t[i] et t[i+1]. Pour i de 0 à n-1 faire # Si l'élément courant est supérieur à l'élément # suivant, les deux éléments sont dans le mauvais ordre. Si t[i] > t[i + 1] alors # Indiquer qu'un échange a été effectué. permuter <-- Vrai # Sauvegarder temporairement la valeur de t[i]. temp <-- t[i] # Placer la valeur suivante dans la position courante. t[i] <-- t[i + 1] # Placer l'ancienne valeur de t[i] # dans la position suivante. t[i + 1] <-- temp Fin pour # Après chaque passage, le plus grand élément # de la partie non triée est placé à la fin. # On réduit donc la partie du tableau à parcourir. n <-- n-1 Fin tant que Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| permuter | booléen |
| min | entier |
| temp | entier |
La procédure afficher
La procédure afficher(t, n) permet d’afficher les n premiers éléments du tableau t.
Elle parcourt les cases du tableau à l’aide de la boucle for, de l’indice 0 jusqu’à n-1. À chaque passage, l’instruction print(t[i]) affiche la valeur contenue dans la case t[i].
|
1 2 3 4 5 6 7 |
Procédure afficher(t:tab; n:entier) # Parcourir les n premières cases du tableau Pour i de 0 à n-1 faire # Afficher chaque élément du tableau Ecrire(t[i]) Finpour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
Programme en Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
# ========================================================== # Importation de la bibliothèque NumPy # ========================================================== from numpy import array # Permet de créer un tableau # ========================================================== # Création du tableau # ========================================================== # Création d'un tableau de 100 éléments initialisés à 0. # Le tableau permettra de stocker les valeurs saisies # par l'utilisateur. t = array([int()] * 100) # ========================================================== # Fonction de saisie de la taille du tableau # ========================================================== def saisie(): # Demander à l'utilisateur de saisir le nombre # d'éléments du tableau. # La valeur doit être comprise entre 2 et 14. n = int(input("donner n entre 2 et 14: ")) # Vérifier que n appartient à l'intervalle [2, 14]. # Tant que la valeur saisie est incorrecte, # on demande une nouvelle valeur. while not (2 <= n <= 14): n = int(input("donner n entre 2 et 14: ")) # Retourner la valeur correcte de n. return n # ========================================================== # Fonction de remplissage du tableau # ========================================================== def remplir(t, n): # Parcourir les n premières cases du tableau. for i in range(n): # Demander à l'utilisateur de saisir un élément # et placer cet élément dans la case t[i]. t[i] = int(input("donner un element du tableau : ")) # ========================================================== # Fonction de tri à bulle # ========================================================== def bulle(t, n): # La variable permuter indique si au moins un échange # a été effectué pendant le passage. # Au départ, on considère qu'un échange est possible. permuter = True # Répéter les passages tant qu'un échange a été effectué # et qu'il reste au moins deux éléments à comparer. while (permuter == True) and (n > 1): # Au début de chaque passage, on considère # qu'aucun échange n'a encore été effectué. permuter = False # Parcourir le tableau en comparant les éléments # voisins t[i] et t[i+1]. for i in range(n - 1): # Si l'élément courant est supérieur à l'élément # suivant, les deux éléments sont dans le mauvais ordre. if t[i] > t[i + 1]: # Indiquer qu'un échange a été effectué. permuter = True # Sauvegarder temporairement la valeur de t[i]. temp = t[i] # Placer la valeur suivante dans la position courante. t[i] = t[i + 1] # Placer l'ancienne valeur de t[i] # dans la position suivante. t[i + 1] = temp # Après chaque passage, le plus grand élément # de la partie non triée est placé à la fin. # On réduit donc la partie du tableau à parcourir. n = n - 1 # ========================================================== # Fonction d'affichage du tableau # ========================================================== def afficher(t, n): # Parcourir les n premières cases du tableau. for i in range(n): # Afficher la valeur contenue dans la case t[i]. print(t[i]) # ========================================================== # Programme principal # ========================================================== # Saisir le nombre d'éléments du tableau. n = saisie() # Afficher un message avant le remplissage du tableau. print("***Remplissage du tableau***") # Remplir le tableau avec les n valeurs saisies # par l'utilisateur. remplir(t, n) # Trier le tableau dans l'ordre croissant # en utilisant l'algorithme du tri à bulle. bulle(t, n) # Afficher un message indiquant que le tableau # a été trié. print("***Tableau trié***") # Afficher les éléments du tableau après le tri. afficher(t, n) |
Exécution du programme
0 commentaire
laisser un commentaire
Passion de robotique
Tutoriels récents
Atelier robotique
Tutoriels populaires
Construction des robots
Tutoriels plus commentés
Bras robotique
Categories
Maison intelligente
