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.
 
Exercice Python Corrigé

2 réflexions sur “Tri par sélection en python

  • janvier 23, 2024 à 9:28 pm
    Permalien

    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
    Répondre

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *