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 10:47]
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 insertion regarde le terme pas encore vu et l'insert entre les nombres regardé plus tôt. Il permet donc le tri du tableau en regardant nombre par nombre et les comparant puis insérant avec ceux vu juste avant.
+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