TD - tri sélection

PDF : Pour impression #

Exercice 1 #

  1. Faire tourner l’algorithme du tri par sélection présenté en cours sur le tableau [5, 7, 3, 1, 9]
  2. Combien de comparaisons sont nécessaires pour trier ce tableau ?
  3. Recommencer avec le tableau déjà trié [1, 3, 5, 7, 9].
  4. Gagne-t-on quelque chose à partir d’un tableau déjà trié ?

Exercice 2 #

  1. Proposer une version avec des indices, en langage naturel du tri par sélection.

  2. Faire tourner votre version sur le tableau [5, 7, 3, 1, 9]

    Compléter le tableau suivant, on écrivant les éléments triés et non triés après chaque tour de la boucle principale.

    Étape Partie triée Partie non triée
    1 [] [5, 7, 3, 1, 9]
    2

Exercice 3 - Vérifier qu’un tableau est trié #

On dispose d’un tableau de nombres, on souhaite vérifier s’il est trié par ordre croissant.

Par exemple : 1, 2, 3, 5, 4, 6, 7 n’est pas trié mais 1, 2, 3, 4, 5, 6, 7 est trié.

  1. Proposer un algorithme permettant de vérifier qu’un tableau de nombres est trié. Quelle devrait en être sa signature ?

  2. Combien de comparaisons sont nécessaire pour s’assurer qu’un tableau est trié ?

  3. Traduire cette fonction en Python

  4. Si ce n’est pas déjà fait, améliorer l’algorithme en quittant dès qu’on repère deux éléments non triés dans le tableau.