Wiki NSI

Outils pour utilisateurs

Outils du site

Piste:
les_programmes_a_connaitre:algorithmique_premiere:tri_selection

Différences

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

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
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]
mm
Ligne 7: Ligne 7:
  
 ====== Comment ça marche ? ====== ====== 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.  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é. 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é 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>  </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é.__+
  
les_programmes_a_connaitre/algorithmique_premiere/tri_selection.txt · Dernière modification: 2023/01/21 18:34 de mm

Outils de la page

Sauf mention contraire, le contenu de ce wiki est placé sous les termes de la licence suivante : CC Attribution-Noncommercial 4.0 International
CC Attribution-Noncommercial 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki