Exercices : tris par sélection et par insertion, recherche dichotomique

ULUMINE · Numérique et sciences informatiques (NSI) · Première

Tris par sélection et par insertion, recherche dichotomique — S’entraîner

Feuille d’exercices

Prénom : ……………………………Date : ……………………Score : ……… / 9

Dérouler les tris et la recherche dichotomique.

1. Exercice 1 — Coche la bonne réponse.

   Quel est le principe du tri par sélection ?

   • Comparer les éléments voisins et les échanger s’ils sont mal rangés
   • Chercher le plus petit élément de la partie non triée et le placer au début de cette partie
   • Insérer chaque élément à sa place dans la partie déjà triée
   • Couper le tableau en deux et trier chaque moitié

2. Exercice 2

   On applique tri_selection à T = [5, 2, 8, 1, 9]. Écris T après le premier tour de la boucle externe (i = 0).

   def tri_selection(T):
       n = len(T)
       for i in range(n - 1):
           imin = i
           for j in range(i + 1, n):
               if T[j] < T[imin]:
                   imin = j
           T[i], T[imin] = T[imin], T[i]

3. Exercice 3

   On applique tri_insertion à T = [5, 2, 8, 1, 9]. Écris T après le tour i = 1.

   def tri_insertion(T):
       for i in range(1, len(T)):
           x = T[i]
           j = i
           while j > 0 and T[j - 1] > x:
               T[j] = T[j - 1]
               j = j - 1
           T[j] = x

4. Exercice 4 — Coche « Vrai » ou « Faux ».

   La recherche dichotomique donne toujours le bon résultat, même si le tableau n’est pas trié.

   VraiFaux

5. Exercice 5

   Avec T = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], que renvoie dichotomie(T, 23) ?

   def dichotomie(T, v):
       g, d = 0, len(T) - 1
       while g <= d:
           m = (g + d) // 2
           if T[m] == v:
               return m
           elif T[m] < v:
               g = m + 1
           else:
               d = m - 1
       return -1

   Écris tes calculs :

   Réponse : ………………

6. Exercice 6

   Pour l’appel dichotomie(T, 23) de l’exercice précédent, combien de tours de la boucle while sont effectués ?

   Écris tes calculs :

   Réponse : ………………

7. Exercice 7 — Coche la bonne réponse.

   Le tri par sélection d’un tableau de n éléments a un coût…

   • constant
   • logarithmique
   • linéaire
   • quadratique

8. Exercice 8

   Combien de comparaisons T[j] < T[imin] le tri par sélection effectue-t-il sur un tableau de 5 éléments ?

   Écris tes calculs :

   Réponse : ………………

9. Exercice 9 — Relie chaque élément de gauche à celui de droite.

   Associe chaque algorithme (tableau de n éléments) à son coût dans le pire des cas.

   1. 1. Accès à T[i]•
   2. 2. Recherche dichotomique•
   3. 3. Recherche séquentielle•
   4. 4. Tri par insertion•

   • •A. linéaire
   • •B. constant
   • •C. logarithmique
   • •D. quadratique

ulumine.com — exercices corrigés gratuits