Différences

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

--- les_programmes_a_connaitre:algorithmique_premiere:tri_selection [2022/12/29 17:31]
mm
+++ les_programmes_a_connaitre:algorithmique_premiere:tri_selection [2023/01/21 18:34] (Version actuelle)
mm
@@ Ligne 7: / Ligne 7: @@
 ====== 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.
@@ Ligne 14: / Ligne 14: @@
 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 ici le minimum et le bleu le "curseur" qui vérifie s'il est plus petit que le minimum enregistré
@@ Ligne 53: / Ligne 53: @@
 </code>
-===== Ancienne Version =====
+===== 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).
-Cet algorithme permet le tri d'un tableau d'entiers en mettant par ordre croissant les nombres présents dans celui-ci.
+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
-**Algorithme:** \\
-{{:les_programmes_a_connaitre:algorithmique_premiere:tri_selection2.png?300 |}}
-<code python>
-"""
-Entrée :    tab : tableau/list -> non trié
-Sortie :    tab : tableau/list -> trié ( dans l'ordre croissant )
-Objectif :  Trié le tableau tab, avec la méthode par sélection
-"""
-def tri_selection(tab):
+{{: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|}}
-   for i in range(len(tab)): # Répétition pour modifier tout le tableau
-       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__ 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