Tri par sélection en python
Nous pouvons créer un programme Python pour trier les éléments d’un tableau à l’aide du tri par sélection. Dans l’algorithme de tri par sélection, nous cherchons l’élément le plus petit et on le met au bon endroit. Nous échangeons l’élément en cours avec le prochain élément le plus petit.
Exemple de Tri par sélection en Python
def tri_selection(tab):
for i in range(len(tab)):
# Trouver le min
min = i
for j in range(i+1, len(tab)):
if tab[min] > tab[j]:
min = j
tmp = tab[i]
tab[i] = tab[min]
tab[min] = tmp
return tab
# Programme principale pour tester le code ci-dessus
tab = [98, 22, 15, 32, 2, 74, 63, 70]
tri_selection(tab)
print ("Le tableau trié est:")
for i in range(len(tab)):
print ("%d" %tab[i])
La sortie:
Le tableau trié est: 2 15 22 32 63 70 74 98
Conclusion
Le tri par sélection fonctionne mieux avec un petit nombre d’éléments. La complexité d’exécution du tri par sélection dans le pire des cas est o(n2) pareil à celle des tri par insertion et par bulle.
- Exécuter un fichier Python en ligne de commande sous Windows
- Comment installer Pip pour Python sur Windows ?
- Algorithme palindrome en Python
- C’est quoi Django? Avantages et inconvénients
- Comment générer une chaîne aléatoire en Python?
- Comment générer un nombre aléatoire en Python?
- Comment vérifier que la valeur entrée est un nombre en Python?
- Nombre de Armstrong en Python
- Vérifier si une année est bissextile en Python
- Algorithme de conversion d’un nombre décimal en binaire Python
- Vérifier si un nombre est pair ou impair en Python
- Factorielle en Python
- Factorielle avec récursivité en Python
- Tri par sélection en python
- Tri par insertion en python
- Tri à bulle en python
- Comment vérifier si une liste est vide en Python
- Compter le nombre d’occurrence d’un caractère dans une chaîne de caractères – Python
- Lire un fichier ligne par ligne en Python
- Comment récupérer le chemin du répertoire courant en Python
- Comment récupérer la date de création/modification d’un fichier en Python
- Comment extraire un fichier zip en Python
- Comment supprimer un répertoire de manière récursive en Python
- Comment vérifier si un fichier ou un dossier existe en Python
- Comment déplacer un fichier ou un répertoire en Python
- Comment créer un répertoire en Python
- Comment lister tous les fichiers d’un répertoire en Python
- Comment supprimer un fichier ou un répertoire en Python
- Comment vérifier si un répertoire est vide en Python
- Comment copier des fichiers d’un endroit à un autre en Python
- Dictionnaire imbriqué en Python
- Comment copier un dictionnaire en Python
- Comment ajouter des paires clé / valeur dans un dictionnaire en Python
- Récupérer une clé dans un dictionnaire à partir d’une valeur en Python
- Vérifier si une chaîne de caractère est contenu dans une autre en Python
- Supprimer les doublons d’une liste en Python
- Comment supprimer plusieurs élément de la liste python
- Convertir un tuple en string python
- Transformer une liste de tuples en liste de listes
- Transformer une liste de tuples en liste python
- Convertir une liste en tuple python
- Convertir une chaîne de caractères en float python
- Convertir une chaîne de caractères en entier python
- Comment transformer une chaîne de caractère en liste python
- Comment transformer une liste en chaîne de caractère python
- Comment trier un dictionnaire par clé ou par valeur en Python
- Comment vérifier si un élément existe dans la liste Python
- Vérifier si tous les éléments d’une liste sont identiques en Python
- Comment fusionner deux listes en Python
- Comment ajouter un élément à un index spécifique dans une liste en Python
- Vérifier si la liste contient tous les éléments d’une autre liste en Python
- Trouver la somme de deux nombres en Python
- Programme Python pour convertir une liste en dictionnaire
- Programme Python pour afficher la suite de Fibonacci
- Programme Python pour afficher tous les nombres premiers d’un intervalle
for i in range( len(tab) – 1 )
Dans le second for, on peut attendre une valeur de i+1 supérieur à la valeur de len(tab)
Python va gérer ce cas et ne pas rentrer dans la boucle mais cela fait une itération de plus pour i inutile.
En effet, si on fait dans le 1er for un range avec len(tab)-1 on éviter une itération. La dernier valeur étant forcément trié
Voici donc une correction possible
for i in range(len(tab)-1): # Trouver le min mini = i for j in range(i+1, len(tab)): if tab[min] > tab[j]: min = j tmp = tab[i] tab[i] = tab[mini] tab[mini] = tmp