====== Tri par sélection ======

[[https://fr.wikipedia.org/wiki/Tri_par_s%C3%A9lection|Page Wikipedia]]

===== 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é.

{{ :nsi:premiere:tableau:tri_selection.svg |}}

<WRAP box>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 ?</WRAP>

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.

<WRAP info>Un algorithme est correct si pour toutes les entrées permises :
  * il termine en un temps fini,
  * il donne la réponse attendue
</WRAP>

==== Terminaison ====

La boucle répétitive s'exécute tant qu'il reste plus d'un item dans la zone jaune.

<WRAP box>**À vous :** justifiez que cette boucle arrive forcément à sa fin.</WRAP>

==== Validité de la réponse ====

On veut prouver qu'à la fin de l'algorithme, les items du tableau sont bien dans l'ordre croissant.

<WRAP box>**À 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
</WRAP>

===== L'algorithme =====

<code lang-none>
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
</code>

<WRAP box>
  - À quoi correspond le ''i'' de la boucle POUR ?
  - Pourquoi ''i'' ne 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 ?
</WRAP>


{{ :nsi:premiere:tableau:tri:tri_selection.cor.pdf |Correction}}