Aller au contenu

Activités II)

Activité II.01

Le schéma ci-dessous illustre le principe de fonctionnement du tri par insertion pour le tableau [27, 10, 12, 8, 11].

Produisez un schéma équivalent pour le tableau [12, 8, 23, 10, 15].

Activité II.02

Le schéma ci-dessous illustre le principe de fonctionnement du tri par sélection pour le tableau [12, 8, 23, 10, 15].

Produisez un schéma équivalent pour le tableau [15, 16, 11, 13, 12].

Activité II.03

Soit l'algorithme du tri par insertion :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
VARIABLE
t : tableau d'entiers
i : nombre entier
j : nombre entier
k : nombre entier
DEBUT
j←2
tant que j<=longueur(t):  
  i←j-1
  k←t[j]
  tant que i>0 et que t[i]>k:
    t[i+1]←t[i]
    i←i-1
  fin tant que
  t[i+1]←k
  j←j+1
fin tant que
FIN

Appliquez cet algorithme au tableau t = [27, 10, 12, 8, 11] et vérifiez que vous obtenez bien le tableau [8, 10, 11, 12, 27].

Activité II.04

Soit l'algorithme du tri par sélection :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
VARIABLE
t : tableau d'entiers
i : nombre entier
min : nombre entier
j : nombre entier
DEBUT
i←1
tant que i<longueur(t):  
  j←i+1
  min←i
  tant que j<=longueur(t):  
    si t[j]<t[min]:
      min←j
    fin si
    j←j+1
  fin tant que
  si min≠i :
    échanger t[i] et t[min]
  fin si
  i←i+1
fin tant que
FIN

Appliquez cet algorithme au tableau t = [27, 10, 12, 8, 11] et vérifiez que vous obtenez bien le tableau [8, 10, 11, 12, 27].

Activité II.05

Proposez une implémentation en Python de l'algorithme de tri par insertion. Vous testerez votre programme à l'aide du tableau t = [15, 16, 11, 13, 12].

Activité II.06

Proposez une implémentation en Python de l'algorithme de tri par sélection. Vous testerez votre programme à l'aide du tableau t = [15, 16, 11, 13, 12].