Wiki NSI

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Algorithme de tri par sélection ======
----

====== Qu'est-ce que c'est ? ======

Un algorithme de tri par sélection est un algorithme qui permet de trier une liste dans l’ordre croissant. Tout en conservant la même structure, c'est-à-dire que le programme conserve la liste d’origine au lieu d’en créé une nouvelle.

====== Comment ça marche ? ======
{{:les_programmes_a_connaitre:algorithmique_premiere:tri_selection1.gif?100 |}}
Dans une Liste à n élément (d’indice 0 à n-1, car on commence par 0 et non par 1), l’algorithme cherche le plus petit entier de la liste et l'échange avec l’élément d’indice 0. 

Rechercher le second plus petit élément du tableau, et l'échanger avec l'élément d'indice 1

Continuer de cette façon jusqu'à ce que le tableau soit entièrement trié.


Le rouge est ici le minimum et le bleu le "curseur" qui vérifie s'il est plus petit que le minimum enregistré

====== Comment on fait ? ======

<code python>

"""
Algorithme de tri par sélection
"""
 
# Initialisation de Variables
t = [1,6,9,3,2,0,7,5,8,4] # Tableau d'entiers
 
"""
Objectif : Algorithme de tri par sélection
Entrée : Liste
Sortie : Liste trié
"""
def tri_select(t):
    for i in range(len(t)-1):
        min = i # min = l'indice du premier élément de la liste non triée
        for j in range(i,len(t)): # Pour la suite de la liste non triée
            if t[j] < t[min] : # si l'élément à l'indice j est plus petit que celui a l'indice min 
                min = j # l'indice min devient alors l'indice j
        t[min],t[i] = t[i],t[min] # échange l'élément à l'indice min avec celui de l'indice i 
    return t
 
#Programme principal
 
print(t)
# [1, 6, 9, 3, 2, 0, 7, 5, 8, 4]
 
print(tri_select(t))
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


</code> 

===== La Complexité =====

La complexité, c'est le nombre de fois que va "boucler" notre programme en fonction de la taille de l'entrée. ex : donner la taille d'une liste sans utiliser la fonction "len()" serait de complexite O(n).

Dans notre cas, la complexité est de O(n²) on appelle cela une complexité quadratique, c'est-à-dire que le nombre d'oppération est proportionnelle au carré de l'entrée 

{{:les_programmes_a_connaitre:algorithmique_premiere:screenshot_from_2023-01-21_18-25-10.png?400|}}{{ :les_programmes_a_connaitre:algorithmique_premiere:screenshot_from_2023-01-21_18-24-52.png?400|}}
Wiki NSI

Outils pour utilisateurs

Outils du site

Outils de la page
