Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
les_programmes_a_connaitre:algorithmique_premiere:tri_selection [2022/12/29 16:51] mm |
les_programmes_a_connaitre:algorithmique_premiere:tri_selection [2023/01/21 18:34] (Version actuelle) mm |
||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
- | #Tri par selection | + | ====== Algorithme de tri par sélection ====== |
+ | ---- | ||
+ | |||
+ | ====== Qu' | ||
+ | |||
+ | 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' | ||
+ | |||
+ | ====== 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' | ||
+ | |||
+ | Rechercher le second plus petit élément du tableau, et l' | ||
+ | |||
+ | Continuer de cette façon jusqu' | ||
+ | |||
+ | |||
+ | Le rouge est ici le minimum et le bleu le " | ||
+ | |||
+ | ====== Comment on fait ? ====== | ||
+ | |||
+ | <code python> | ||
+ | |||
+ | """ | ||
+ | Algorithme de tri par sélection | ||
+ | """ | ||
+ | |||
+ | # Initialisation de Variables | ||
+ | t = [1, | ||
+ | |||
+ | """ | ||
+ | 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' | ||
+ | for j in range(i, | ||
+ | if t[j] < t[min] : # si l' | ||
+ | min = j # l' | ||
+ | t[min],t[i] = t[i],t[min] # échange l' | ||
+ | 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] | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | ===== La Complexité ===== | ||
+ | |||
+ | La complexité, | ||
+ | |||
+ | Dans notre cas, la complexité est de O(n²) on appelle cela une complexité quadratique, | ||
+ | |||
+ | {{: |