Algorithme : Tri par sélection du tableau des entiers
Plan de tutoriel
1- Principe du tri par sélection
2- Algorithme du tri par sélection
3- Programme Python
Principe du tri par sélection
Le tri par sélection 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 à rechercher, à chaque étape, le plus petit élément dans la partie qui n’est pas encore triée.
Une fois le plus petit élément trouvé, on l’échange avec le premier élément de la partie non triée. Cet élément est alors placé définitivement à sa position correcte. Le même processus est ensuite répété pour les éléments restants du tableau.
Par exemple, pour le tableau [64, 25, 12, 22, 11], le premier passage consiste à rechercher le plus petit élément, qui est 11, puis à l’échanger avec 64. Le tableau devient alors [11, 25, 12, 22, 64]. Au passage suivant, on recherche le minimum parmi [25, 12, 22, 64], qui est 12, et on l’échange avec 25.
Le processus continue jusqu’à ce que tous les éléments soient placés dans leur position définitive. Le tableau obtenu est alors [11, 12, 22, 25, 64]. Ainsi, à chaque passage, la partie triée du tableau augmente d’un élément tandis que la partie non triée diminue.
Algorithme du tri par sélection
Dans cet algorithme, On va utiliser deux fonctions et trois procédures :
- la fonction saisie
- la procédure remplir
- la procédure selection
Algorithme du programme Principal
L’algorithme principal tri_selection constitue le point de départ du programme. Il organise les différentes étapes nécessaires pour réaliser le tri par sélection d’un tableau d’entiers.
Au début, l’instruction n ← saisie() permet de saisir le nombre d’éléments du tableau. Ensuite, la procédure remplir(t,n) permet de remplir le tableau t avec les n entiers saisis par l’utilisateur. La procédure selection(t,n) applique ensuite l’algorithme du tri par sélection afin de classer les éléments du tableau dans l’ordre croissant. Enfin, l’instruction afficher(t,n) permet d’afficher le tableau après le tri.
Ainsi, l’algorithme principal assure l’enchaînement des différentes opérations : saisie du nombre d’éléments, remplissage du tableau, tri des éléments et affichage du résultat.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
Algorithme tri_selection 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 la méthode du tri par sélection. selection(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 selection
La procédure selection permet de trier le tableau t dans l’ordre croissant en utilisant la méthode du tri par sélection.
|
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 |
Procédure selection(var t:tab;n:entier) # Parcourir le tableau jusqu'à l'avant-dernière position. # À chaque étape, on cherche le plus petit élément # dans la partie non encore triée. Pour i de 0 à n-2 faire # On considère au départ que l'élément situé à la position i # est le plus petit. min <-- i # Rechercher le plus petit élément dans la partie # du tableau située après la position i. Pour j de i+1 à n-1 faire # Comparer l'élément considéré comme minimum # avec l'élément situé à la position j. Si t[min] > t[j] alors # Si t[j] est plus petit, mémoriser sa position. min <-- j Fin si Fin pour # Si le minimum n'est pas déjà à la position i, # effectuer un échange entre les deux éléments. Si i != min alors temp <-- t[i] # Sauvegarder temporairement t[i] t[i] <-- t[min] # Placer le minimum à la position i t[min] <-- temp # Placer l'ancien t[i] à la position du minimum Fin si Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
| min | entier |
| temp | entier |
La procédure afficher
La fonction binaire_vers_hexa() permet de convertir deux groupes de bits représentant un octet binaire en une valeur sous forme hexadécimale. Elle prend en entrée deux chaînes binaires (b1 et b2) correspondant généralement aux deux demi-octets d'un octet.
La fonction commence par convertir le premier groupe binaire b1 en une valeur décimale. Si cette valeur est inférieure à 10, elle est conservée sous forme de chiffre ; sinon, elle est convertie en caractère hexadécimal (A à F). Ensuite, elle convertit le deuxième groupe binaire b2 en valeur décimale.
Enfin, elle retourne la représentation hexadécimale obtenue en combinant la valeur du deuxième groupe avec le caractère correspondant au premier groupe. Cette fonction est utilisée pour transformer une donnée binaire en une écriture hexadécimale plus compacte et plus lisible.
|
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 |
Solution 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 |
# ========================================================== # Importation de la bibliothèque NumPy # ========================================================== from numpy import array # Permet de créer et manipuler des tableaux # ========================================================== # 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 # 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 est incorrecte, on redemande la saisie. 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 le placer dans la case t[i]. t[i] = int(input("donner un element du tableau : ")) # ========================================================== # Fonction de tri par sélection # ========================================================== def selection(t, n): # Parcourir le tableau jusqu'à l'avant-dernière position. # À chaque étape, on cherche le plus petit élément # dans la partie non encore triée. for i in range(n - 1): # On considère au départ que l'élément situé à la position i # est le plus petit. min = i # Rechercher le plus petit élément dans la partie # du tableau située après la position i. for j in range(i + 1, n): # Comparer l'élément considéré comme minimum # avec l'élément situé à la position j. if t[min] > t[j]: # Si t[j] est plus petit, mémoriser sa position. min = j # Si le minimum n'est pas déjà à la position i, # effectuer un échange entre les deux éléments. if i != min: temp = t[i] # Sauvegarder temporairement t[i] t[i] = t[min] # Placer le minimum à la position i t[min] = temp # Placer l'ancien t[i] à la position du minimum # ========================================================== # Fonction d'affichage du tableau # ========================================================== def afficher(t, n): # Parcourir les n premières cases du tableau for i in range(n): # Afficher chaque élément du tableau print(t[i]) # ========================================================== # Programme principal # ========================================================== # Saisir la taille du tableau n = saisie() # Afficher un message avant le remplissage print("***Remplissage du tableau***") # Remplir le tableau avec les valeurs saisies remplir(t, n) # Trier le tableau dans l'ordre croissant # en utilisant la méthode du tri par sélection. selection(t, n) # Afficher un message indiquant que le tableau est trié print("***Tableau trié***") # Afficher les éléments du tableau 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
