Algorithme : Tri par insertion du tableau des entiers
Plan de tutoriel
1- Principe du tri par insertion
2- Algorithme du tri par insertion
3- Programme Python
Principe du tri par insertion
Le tri par insertion consiste à trier les éléments d’un tableau progressivement. Le premier élément est considéré comme déjà trié. Ensuite, on prend chaque élément suivant et on le compare avec les éléments qui le précèdent afin de trouver sa position correcte.Dans le programme, la variable e permet de mémoriser l’élément à insérer, tandis que la variable j indique sa position. On compare e avec l’élément situé juste avant. Si cet élément est plus grand que e, il est décalé d’une position vers la droite. Cette opération est répétée jusqu’à trouver la position correcte de e.Enfin, l’élément e est placé dans la position trouvée. Ainsi, après chaque insertion, la partie gauche du tableau reste triée. Le processus continue jusqu’au dernier élément, ce qui permet d’obtenir finalement un tableau entièrement trié dans l’ordre croissant.
Algorithme du tri par insertion
Dans cet algorithme, On va utiliser deux fonctions et trois procédures :
- la fonction saisie
- la procédure remplir
- la procédure insertion
Algorithme du programme Principal
Le programme principal permet d’exécuter les différentes étapes du tri par insertion dans le bon ordre. Il commence par appeler la fonction saisie() pour demander à l’utilisateur le nombre d’éléments du tableau et vérifier que cette valeur est correcte.
Ensuite, il appelle la fonction remplir(t, n) pour remplir le tableau avec les valeurs saisies par l’utilisateur. Après le remplissage, la fonction insertion(t, n) est appelée pour trier les éléments du tableau dans l’ordre croissant à l’aide de l’algorithme du tri par insertion.
Enfin, le programme affiche un message indiquant que le tableau est trié, puis appelle la fonction afficher(t, n) pour 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_insertion 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 les n éléments du tableau dans l'ordre croissant # en utilisant l'algorithme du tri par insertion. insertion(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 insertion
La procédure insertion(t, n) permet de trier les n premiers éléments du tableau t dans l’ordre croissant en utilisant l’algorithme du tri par insertion.
|
1 2 3 4 5 6 7 8 9 10 |
Procédure insertion(var t:tab;n:entier) Pour i de 1 à n-1 faire j<-- i e<--T[i] Tant que (t[j-1]>e) et (j>1) faire t[j]<--t[j-1] j<--j-1 Fin tantque t[j]<--e Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
| e | 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 |
# ========================================================== # Importation de la bibliothèque NumPy # ========================================================== from numpy import array # Importer la fonction array de NumPy. # Elle permet de créer un tableau. # ========================================================== # Création du tableau # ========================================================== # Créer un tableau de 100 éléments. # Toutes les cases sont initialisées à 0. # Seules les n premières cases seront utilisées. 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. n = int(input("donner n entre 2 et 14: ")) # Vérifier que n est compris entre 2 et 14. # Tant que n n'est pas valide, demander une nouvelle saisie. while not (2 <= n <= 14): # Demander à nouveau la valeur de n. 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. # La valeur saisie est convertie en entier # puis stockée dans la case t[i]. t[i] = int(input("donner un element du tableau : ")) # ========================================================== # Fonction de tri par insertion # ========================================================== def insertion(t, n): # Parcourir le tableau à partir du deuxième élément. # L'élément situé à la position i sera inséré # à sa bonne position parmi les éléments précédents. for i in range(1, n): # j représente la position de l'élément à déplacer. j = i # Mémoriser l'élément à insérer dans la partie déjà triée. e = t[i] # Comparer e avec les éléments précédents. # Si l'élément précédent est plus grand que e, # il est déplacé d'une position vers la droite. # # j > 1 permet de ne pas dépasser la première case # du tableau. while (t[j-1] > e) and (j > 1): # Décaler l'élément t[j-1] vers la droite. t[j] = t[j-1] # Reculer d'une position pour continuer la comparaison. j = j - 1 # Placer l'élément e à sa position correcte. t[j] = e # ========================================================== # 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 # ========================================================== # Appeler la fonction saisie() pour obtenir # le nombre d'éléments du tableau. n = saisie() # Afficher un message avant le remplissage du tableau. print("***Remplissage du tableau***") # Appeler la fonction remplir() pour saisir # les n éléments du tableau. remplir(t, n) # Trier les n éléments du tableau dans l'ordre croissant # en utilisant l'algorithme du tri par insertion. insertion(t, n) # Afficher un message après le tri. print("***Tableau trié***") # Afficher les n é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
