Différences

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

--- les_programmes_a_connaitre:algorithmique_premiere:tri_selection [2021/01/26 10:55]
rd
+++ les_programmes_a_connaitre:algorithmique_premiere:tri_selection [2022/12/29 17:27]
mm
@@ Ligne 1: / Ligne 1: @@
-====== Algorithme de tri par sélection:======
+====== 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 ? ======
+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é.
+{{:les_programmes_a_connaitre:algorithmique_premiere:tri_selection1.gif|}} \\ \\
+Le rouge est ic le minimum et le bleu le "cursseur" qui vérifie si il est plus petit que le 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>
+===== Ancienne Version =====
@@ Ligne 8: / Ligne 61: @@
 {{:les_programmes_a_connaitre:algorithmique_premiere:tri_selection2.png?300 |}}
 <code python>
-i=1
+"""
-while i<len(t):
+Entrée :    tab : tableau/list -> non trié
-    j=i+1
+Sortie :    tab : tableau/list -> trié ( dans l'ordre croissant )
-    mini=i
+Objectif :  Trié le tableau tab, avec la méthode par sélection
-    while j<len(t):
+"""
-        if t[j]<t[mini]:
-            mini=j
+def tri_selection(tab):
-        j=j+1
-    if mini!=i:
+   for i in range(len(tab)): # Répétition pour modifier tout le tableau
-        # échanger t[i] et t[mini]
-    i=i+1
+       min = i # Intialisation de Variable
+       for j in range(i+1, len(tab)): # Pour balayer tout le tableau
+           if tab[min] > tab[j]: # Si on trouve un nombre plus petit
+               min = j # Décalage
+       k = tab[i] # Décalage
+       tab[i] = tab[min] # Décalage
+       tab[min] = k # Décalage
+   return tab # Renvoyer tab
 </code> \\
 {{  :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é qui ne changera pas mais qui s'agrandira jusqu'à ce qu'elle atteigne la taille du tableau de base. En trouvant le nombre le plus petit, il échange sa place avec celui qui est juste après la partie du tableau triée.
+La méthode par __sélection__ divise tout d’abord le tableau ( liste ) en deux : une partie triée et une autre non triée, pour délimiter cela il y a des bornes ( représenter par des variable, souvent appelés “ debut” et “fin” ). Contrairement à celle par insertion cette méthode __cherche le plus petit élément du tableau__ ( de la partie non trié ) puis cette élément __échange sa place avec celui qui est à la première place du tableau non trié__ et après ce décalage __il fera partie de la partie trié.__

Wiki NSI

Outils pour utilisateurs

Outils du site

Différences

Outils de la page