Algorithme : Tri RAPIDE du tableau des entiers
Plan de tutoriel
1- Principe du tri de RAPIDE
2- Algorithme du tri de RAPIDE
3- Programme Python
Principe du tri de Rapide
Le tri rapide (Quick Sort) est un algorithme de tri basé sur le principe « diviser pour régner ». Son objectif est de trier un tableau dans l’ordre croissant en le divisant progressivement en plusieurs parties plus petites.
Tout d’abord, l’algorithme choisit un élément du tableau appelé pivot. Dans votre programme, le pivot est le premier élément de la partie du tableau à trier, c’est-à-dire t[g].
Ensuite, l’algorithme effectue une partition du tableau autour du pivot. Il recherche, à partir de la gauche, un élément qui est supérieur ou égal au pivot et, à partir de la droite, un élément qui est inférieur au pivot. Lorsque ces deux éléments sont trouvés, ils sont échangés.
Après les échanges, le pivot est placé à sa position définitive. Tous les éléments situés à gauche du pivot sont alors inférieurs ou égaux au pivot, tandis que les éléments situés à droite sont supérieurs ou égaux au pivot.
L’algorithme recommence ensuite le même processus sur les deux parties obtenues : la partie gauche du pivot et la partie droite du pivot. Cette opération est réalisée de manière récursive, jusqu’à ce que chaque partie ne contienne plus qu’un seul élément ou aucun élément.
Ainsi, le tri rapide permet de transformer progressivement un tableau non trié en un tableau trié. En moyenne, sa complexité est de O(n log n), ce qui en fait un algorithme de tri généralement très efficace.
Algorithme du tri de RAPIDE
Dans cet algorithme, On va utiliser deux fonctions et deux procédures :
- la fonction saisie
- la procédure remplir
- la fonction tri_rapide
- la procédure tri
Algorithme du programme Principal
Le rôle du programme principal est de coordonner les différentes étapes du tri rapide : saisir la taille du tableau, remplir le tableau, lancer le tri, puis afficher le résultat.
1- Saisie de la taille du tableau
La fonction saisie() demande à l'utilisateur le nombre n d'éléments à traiter.
2- Remplissage du tableau
La fonction remplir(t, n) permet de saisir les n valeurs entières du tableau.
3- Tri du tableau
L'instruction tri(t, 0, n - 1) lance l'algorithme du tri rapide (Quick Sort) sur l'ensemble du tableau, de l'indice 0 jusqu'à l'indice n-1.
3- Affichage du tableau trié
Enfin, la fonction afficher(t, n) affiche les éléments du tableau après leur classement dans l'ordre croissant.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
Algorithme tri_shell Debut # Appeler la fonction saisie() pour obtenir # le nombre d'éléments du tableau. n <-- saisie() # Afficher un message avant le remplissage du tableau. Ecrire("***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. # Le tri rapide commence à l'indice 0 # et se termine à l'indice n-1. tri(t, 0, n - 1) # Afficher un message après le tri. Ecrire("***Tableau trié***") # Afficher les n éléments du tableau après le 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 tri
La procédure tri(t, g, d) a pour rôle de trier récursivement une partie du tableau t dans l’ordre croissant, en utilisant l’algorithme du tri rapide (Quick Sort).
Rôle de la procédure tri
t : tableau contenant les entiers à trier.
g : indice de début de la partie du tableau à trier.
d : indice de fin de cette partie.
La procédure fonctionne ainsi :
1- Définir les limites de la partie à trier
index_gauche = g et index_droit = d indiquent les bornes de la zone de travail.
2- Vérifier qu'il reste au moins deux éléments
La condition index_gauche < index_droit permet de poursuivre le tri uniquement si la partie contient plusieurs éléments. 3- Effectuer une partition
tri_rapide(t, index_gauche, index_droit) réorganise les éléments autour d'un pivot et retourne sa position index.
4- Trier la partie gauche
L'appel : tri(t, index_gauche, index - 1) trie récursivement les éléments situés avant le pivot.
5- Trier la partie droite
L'appel : tri(t, index + 1, index_droit) trie récursivement les éléments situés après le pivot.
|
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 |
Procédure TRI(var t:tab; g:entier; d:entier) : # index_gauche représente le début # de la partie du tableau à trier. index_gauche <-- g # index_droit représente la fin # de la partie du tableau à trier. index_droit <-- d # Vérifier que la partie du tableau contient # au moins deux éléments. Si (index_gauche < index_droit) alors # Effectuer la partition de la partie du tableau. # La fonction retourne la position du pivot. index <-- tri_rapide(t, index_gauche, index_droit) # Trier récursivement la partie située # à gauche du pivot. tri(t, index_gauche, index - 1) # Trier récursivement la partie située # à droite du pivot. tri(t, index + 1, index_droit) Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| index_gauche | entier |
| index_droit | entier |
| index | entier |
La fonction tri_rapide
La fonction tri_rapide(t, g, d) a pour rôle de réaliser la partition d'une partie du tableau dans l'algorithme du tri rapide. Elle utilise le premier élément t[g] comme pivot, réorganise les éléments autour de ce pivot, puis retourne sa position définitive.
Rôle de la fonction tri_rapide
t : tableau d'entiers à trier.
g : indice de début de la partie à trier.
d : indice de fin de la partie à trier.
l : indice qui parcourt le tableau de gauche vers la droite.
m : indice qui parcourt le tableau de droite vers la gauche.
t[g] : élément choisi comme pivot.
Fonctionnement
1- Initialisation des indices
l commence à g + 1 et m commence à d. Les deux indices vont parcourir la partie du tableau située autour du pivot.
2- Recherche à gauche
L'indice l avance tant que les éléments rencontrés sont inférieurs au pivot.
3- Recherche à droite
L'indice m recule tant que les éléments rencontrés sont supérieurs ou égaux au pivot.
4- Échange des éléments
Lorsque l trouve un élément trop grand et m trouve un élément trop petit, les deux éléments sont échangés. Cela permet de placer les petites valeurs à gauche et les grandes valeurs à droite.
5- Placement du pivot
Lorsque les recherches sont terminées, le pivot est échangé avec t[m] s'il est nécessaire. Le pivot se retrouve alors à sa position définitive.
6- Retour de la position du pivot
retourner m retourne l'indice où le pivot a été placé. La procédure tri() utilise ensuite cette position pour trier récursivement les deux parties du tableau.
|
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 |
Fonction tri_rapide(var t:tab; g:entier; d:entier) : entier # l représente l'indice de recherche à gauche. # Il commence juste après le pivot. l <-- g + 1 # m représente l'indice de recherche à droite. # Il commence à la fin de la partie à trier. m <-- d # Le pivot est l'élément situé à la position g. # Il sera placé à sa position définitive # à la fin de la partition. # Continuer les recherches tant que # les indices l et m ne se sont pas croisés. Tant que (l < m) faire # Chercher à partir de la gauche un élément # qui est supérieur ou égal au pivot. Tant que (l < m) et (t[g] > t[l]) faire # Avancer l'indice gauche. l <-- l + 1 Fin tant que # Chercher à partir de la droite un élément # qui est inférieur au pivot. Tant que (l <= m) et (t[g] <= t[m]) faire # Reculer l'indice droit. m <-- m - 1 Fin tantque # Si les deux indices ne se sont pas croisés, # échanger les éléments t[l] et t[m]. Si (l < m) alors # Sauvegarder temporairement t[l]. aux <-- t[l] # Placer t[m] dans la case t[l]. t[l] <-- t[m] # Placer l'ancienne valeur de t[l] dans la case t[m]. t[m] <-- aux # Avancer l'indice gauche. l <-- l + 1 # Reculer l'indice droit. m <-- m - 1 # Lorsque les recherches sont terminées, Fin si # vérifier si le pivot doit être échangé avec t[m]. Si (t[g] > t[m]) alors # Sauvegarder temporairement la valeur du pivot. aux <-- t[g] # Placer t[m] à la position du pivot. t[g] <-- t[m] # Placer le pivot à la position m. t[m] <-- aux Fin si # Retourner la position définitive du pivot. return m Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| l | entier |
| m | entier |
| aux | 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 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 |
# ========================================================== # Importation de la bibliothèque NumPy # ========================================================== from numpy import array # Importer la fonction array de NumPy. # Elle permet de créer et de manipuler des tableaux. # ========================================================== # 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, effectuer # 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. # Elle est ensuite placée dans la case t[i]. t[i] = int(input("donner un element du tableau : ")) # ========================================================== # Fonction de partition du tri rapide # ========================================================== def tri_rapide(t, g, d): # l représente l'indice de recherche à gauche. # Il commence juste après le pivot. l = g + 1 # m représente l'indice de recherche à droite. # Il commence à la fin de la partie à trier. m = d # Le pivot est l'élément situé à la position g. # Il sera placé à sa position définitive # à la fin de la partition. # Continuer les recherches tant que # les indices l et m ne se sont pas croisés. while (l < m): # Chercher à partir de la gauche un élément # qui est supérieur ou égal au pivot. while (l < m) and (t[g] > t[l]): # Avancer l'indice gauche. l = l + 1 # Chercher à partir de la droite un élément # qui est inférieur au pivot. while (l <= m) and (t[g] <= t[m]): # Reculer l'indice droit. m = m - 1 # Si les deux indices ne se sont pas croisés, # échanger les éléments t[l] et t[m]. if (l < m): # Sauvegarder temporairement t[l]. aux = t[l] # Placer t[m] dans la case t[l]. t[l] = t[m] # Placer l'ancienne valeur de t[l] # dans la case t[m]. t[m] = aux # Avancer l'indice gauche. l = l + 1 # Reculer l'indice droit. m = m - 1 # Lorsque les recherches sont terminées, # vérifier si le pivot doit être échangé avec t[m]. if (t[g] > t[m]): # Sauvegarder temporairement la valeur du pivot. aux = t[g] # Placer t[m] à la position du pivot. t[g] = t[m] # Placer le pivot à la position m. t[m] = aux # Retourner la position définitive du pivot. return m # ========================================================== # Fonction principale du tri rapide # ========================================================== def tri(t, g, d): # index_gauche représente le début # de la partie du tableau à trier. index_gauche = g # index_droit représente la fin # de la partie du tableau à trier. index_droit = d # Vérifier que la partie du tableau contient # au moins deux éléments. if (index_gauche < index_droit): # Effectuer la partition de la partie du tableau. # La fonction retourne la position du pivot. index = tri_rapide(t, index_gauche, index_droit) # Trier récursivement la partie située # à gauche du pivot. tri(t, index_gauche, index - 1) # Trier récursivement la partie située # à droite du pivot. tri(t, index + 1, index_droit) # ========================================================== # Procédure 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) # ========================================================== # Tri du tableau # ========================================================== # Trier les n éléments du tableau dans l'ordre croissant. # Le tri rapide commence à l'indice 0 # et se termine à l'indice n-1. tri(t, 0, n - 1) # 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
1 commentaire
Brock 01-09-2626
Valuable information. Lucky me I found your web site unintentionally, and I'm stunned why this twist of fate did not came about in advance! I bookmarked it.
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
