Table des matières
Tri par sélection
Principe
Tout le long de l'algorithme, on considère deux zones du tableau. L'une à gauche – sur fond orange dans l'exemple – et l'autre à droite – sur fond jaune dans l'exemple.
L'algorithme est constitué principalement d'une boucle répétitive. À chaque exécution de cette boucle, on sélectionne le plus petit élément parmi les jaunes et on le déplace à la suite de la zone orange. La zone orange s'en trouve augmentée d'un élément – ce qui diminue la jaune.
La boucle s'arrête quand la zone jaune ne compte plus qu'un seul élément. Le tableau est alors trié.
Le tableau donné en exemple contient 8 items. Combien de recherche de plus petit élément doit-on faire ? Et si le tableau contenait n items ?
La recherche du plus petit élément est plus ou moins coûteuse selon le nombre d'items à considérer. Dans l'exemple, lors du premier passage, il faut chercher parmi 8 items ; lors du 2e passage, parmi 7 items… Ce cumul donne une bonne estimation du nombre de calculs élémentaires nécessaires pour ce tri :
$$8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36$$
Preuve de correction
On profite de notre travail sur les algorithmes de tri pour réfléchir aux problèmes de correction.
Un algorithme est correct si pour toutes les entrées permises :
- il termine en un temps fini,
- il donne la réponse attendue
Terminaison
La boucle répétitive s'exécute tant qu'il reste plus d'un item dans la zone jaune.
À vous : justifiez que cette boucle arrive forcément à sa fin.
Validité de la réponse
On veut prouver qu'à la fin de l'algorithme, les items du tableau sont bien dans l'ordre croissant.
À vous : justifiez que :
- les items de la zones oranges sont toujours inférieurs ou égaux à ceux de la zone jaune,
- les items de la zone orange sont dans l'ordre
- le tableau est dans l'ordre à la fin de l'exécution
L'algorithme
FONCTION tri_par_selection
ENTRÉE: tab, le tableau à trier
La fonction ne renvoie rien, le tableau est trié en place
DÉBUT
soit n le nombre d'éléments de tab
POUR i ALLANT DE 0 À n - 2 compris FAIRE
m = i
POUR j ALLANT DE i+1 à n-1 compris FAIRE
SI tab[j] < tab[m] ALORS
m = j
FIN SI
FIN POUR
intervertir tab[m] et tab[i]
FIN POUR
FIN
- À quoi correspond le
ide la boucle POUR ? - Pourquoi
ine va que jusqu'àn - 2? - Implémentez cet algorithme en Python.
- En fonction de
n, et en considérant que chaque ligne de votre programme s'exécute en un temps T, quelle sera la durée totale de ce tri ?