Différences

Ci-dessous, les différences entre deux révisions de la page.

--- les_programmes_a_connaitre:algorithmique_premiere:tri_selection [2021/01/12 11:03]
rd
+++ les_programmes_a_connaitre:algorithmique_premiere:tri_selection [2023/01/21 18:34] (Version actuelle)
mm
@@ Ligne 1: / Ligne 1: @@
-====== Algorithme de tri par sélection:======
+====== Algorithme de tri par sélection ======
 ----
+====== Qu'est-ce que c'est ? ======
-Cet algorithme permet le tri d'un tableau d'entiers en mettant par ordre croissant les nombres présent dans celui-ci.
+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 ? ======
-**Algorithme:** \\
-{{:les_programmes_a_connaitre:algorithmique_premiere:tri_selection2.png?300 |}}
 <code python>
-i=1
-while i<len(t):
+"""
-    j=i+1
+Algorithme de tri par sélection
-    mini=i
+"""
-    while j<len(t):
-        if t[j]<t[mini]:
+# Initialisation de Variables
-            mini=j
+t = [1,6,9,3,2,0,7,5,8,4] # Tableau d'entiers
-        j=j+1
-    if mini!=i:
+"""
-        # échanger t[i] et t[mini]
+Objectif : Algorithme de tri par sélection
-    i=i+1
+Entrée : Liste
-</code> \\
+Sortie : Liste trié
-{{  :les_programmes_a_connaitre:algorithmique_premiere:tri_selection1.gif|}} \\ \\
+"""
-La méthode par __sélection__ contrairement à celle par insertion regarde en premier le nombre le plus petit dans le tableau terme par terme et le positionne ensuite au début. Il y a donc une partie dans le tableau triée qui ne changera pas mais qui s'agrandira jusqu'à ce qu'elle atteint la taille du tableau de base. En trouvant le nombre le plus petit, il échange sa place ave celui qui est juste après la partie du tableau triée.
+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

Différences

Outils de la page