Les deux révisions précédentes
Révision précédente
Prochaine révision
|
Révision précédente
Prochaine révision
Les deux révisions suivantes
|
les_programmes_a_connaitre:algorithmique_premiere:tri_selection [2021/01/26 10:54] rd |
les_programmes_a_connaitre:algorithmique_premiere:tri_selection [2022/12/29 17:02] mm |
====== Algorithme de tri par sélection:====== | ====== Algorithme de tri par sélection ====== |
---- | ---- |
| |
| =====C'est Quoi ? ===== |
| |
Cet algorithme permet le tri d'un tableau d'entiers en mettant par ordre croissant les nombres présents dans celui-ci. | Cet algorithme permet le tri d'un tableau d'entiers en mettant par ordre croissant les nombres présents dans celui-ci. |
{{:les_programmes_a_connaitre:algorithmique_premiere:tri_selection2.png?300 |}} | {{:les_programmes_a_connaitre:algorithmique_premiere:tri_selection2.png?300 |}} |
<code python> | <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> \\ | </code> \\ |
{{ :les_programmes_a_connaitre:algorithmique_premiere:tri_selection1.gif|}} \\ \\ | {{ :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ée qui ne changera pas mais qui s'agrandira jusqu'à ce qu'elle atteint la taille du tableau de base. En trouvant le nombre le plus petit, il échange sa place ave 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é.__ |
| |