Les méthodes de tri d’un tableau :
1. Introduction :
Le tri consiste à mettre dans un ordre (croissant ou décroissant) un ensemble
d’éléments,généralement, un tableau.
a. Énoncé pour tous le chapitre :
On se propose de remplir un tableau T de n éléments (1<n<20) par des entiers,
le trier parordre croissant et l’afficher.
Exemple n= 4
T 15 0 10 50 …………..
T 0 10 15 50 …………..
b. Algorithme du programme principal :
2. Tri par sélection :
On va se concentrer sur le module TRIER en utilisant les 2 méthodes de tri
suivantes : le tripar sélection et le tri par insertion
a. Principe :
1) On cherche le pos_min, l’emplacement de l’élément le plus petit du tableau en
comparant son contenu avec t[1], s’ils sont différents , on les permute. Donc t [1]
contient la plus petite valeur.
2) Le sous tableau de t allant de 2 à n est non trié, on répète les étapes 1) et 2) et
ainsi de suite jusqu’à l’avant dernier élément (n-1).
39
Prenons désormais comme exemple la suite de nombres suivante :
6, 1, 9, 3. Trions cette suite avec l’algorithme du tri par sélection
dans l’ordre croissant :
1er tour :
6, 1, 9, 3 -> le plus petit élément du tableau est 1,
on le place donc sur la première case (en
l'échangeant avec le 6).
2ème tour :
1, 6, 9, 3 -> le deuxième plus petit élément est 3,
on le place sur la deuxième case et on l’échange
avec le 6.
3ème tour :
1, 3, 9, 6 -> le troisième plus petit élément est 6, on
l’échange avec 9 pour le placer sur la troisième
case.
4ème tour :
1, 3, 6, 9 -> le quatrième plus petit élément du
tableau est 9, il est déjà en quatrième position on
ne fait rien.
b. Exemple :
Exécuter le principe du tri par sélection sur le tableau suivant :
N=6 et T= 15 0 10 50 30 25
40
c. Algorithme trier et ses modules
……………………………………………………………………
……………………………………………………………………
Objet Type/Nature
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
…………………………………………………………………… Objet Type/Nature
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
3. Tri par insertion :
a. Principe : Il consiste à :
1 Chercher la position de l’ième élément dans la partie qui le précède (de 1 a i-1) tout en
considérant que cette partie est triée et cherchant à la garder triée. Si je dois changer
l’emplacement de cet ième élément a un emplacement j, alors décaler à droite tous les
éléments de j a i-1.
2 Insérer ensuite l’ième élément dans la case j.
41
Prenons comme exemple la suite de nombre suivante : 9, 2, 7, 1 que l’on
veut trier en ordre croissant avec l’algorithme du tri par insertion :
1er tour :
9 | 2, 7, 1 -> à gauche la partie triée du tableau (le
premier élément est considéré comme trié puisqu'il est
seul dans cette partie), à droite la partie non triée. On
prend le premier élément de la partie non triée, 2, et on
l'insère à sa place dans la partie triée, c'est-à-dire à
gauche de 9.
2ème tour :
2, 9 | 7, 1 -> on prend 7, et on le place entre 2 et 9 dans
la partie triée.
3ème tour :
2, 7, 9 | 1 -> on continue avec 1 que l’on place au début
de la première partie.
b. Exemple :
Exécuter le principe du tri par sélection sur le tableau suivant :
N=6 et T= 15 0 10 50 30 25
42
Remarque :
Cette méthode de tri nécessite l’utilisation d’une variable
intermédiaire pour conserver la valeur à insérer.
Le premier élément (t[1]) est considéré trié.
c. Algorithme trier et ses modules
……………………………………………………………………
……………………………………………………………………
Objet Type/Nature
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
…………………………………………………………………… Objet Type/Nature
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
……………………………………………………………………
43
Série d’exercices : les tris de tableau
Exercice 1 :
Écrire un programme qui permet de saisir un numéro de carte d’identité CIN d’une personne
puis afficher le plus grand nombre formé par ses chiffres.
NB. Un CIN est un nombre composé de 8 chiffres commençant soit par 0soit par 1
Ex :Si CIN = 16382515 alors le programme affichera le plus grand nombre formé par les
chiffres de ce cin est 86553211
Exercice 2 :
On se propose de ranger dans un tableau V les numéros des cartes d’identité nationale des
Nélèves d’un lycée. (8 ≤ N ≤ 25)
Deux élèves ne peuvent pas avoir un même numéro de carte d’identité nationale. Un
numéro de carte d’identité est composé obligatoirement de huit chiffres.
Écrire l’algorithme puis un programme Python qui permet de saisir les numéros de cartes
d’identité de N élèves du lycée, de les afficher puis de calculer le plus grand numéro de CIN
résultant de la concaténation desplus grands chiffres des CINs utilisés dans V.
Ex : si N = 9 et V= {09586725, 15263800,15263412, 51723070, 45211300, 75933012,
11022301, 12233423 , 0122321 0}
Alors le programme affichera 99876543
Exercice 3 :
Écrire l’algorithme puis un programme Python qui permet de :
- Saisir n entiers de 6 chiffres dans un tableau t avec 5≤n≤25
- Saisir aléatoirement un entier k tel que 1≤k≤6
- Trier le tableau T par ordre décroissant selon le kème chiffre de T[i] puis par
ordre décroissantselon la valeur de T[i]
- Afficher T tel que 3 éléments par ligne.
Ex : Si n= 10 et k=2 et
T= {253462, 100000, 685923, 452136, 968543, 326758, 142536, 785643, 956832,
102534}
Alors le programme doit trier T par ordre décroissant selon les 2èmes chiffres de T[i]
Donc T devient {785643, 685923, 968543, 956832, 452136, 253462, 142536, 326758,
102534,
100000}
Puis afficher : 785643 685923 968543
956832 452136 253462
142536 326758 102534
100000
44
Exercice 4 :
Écrire un programme qui permet de :
Remplir un tableau T par N entiers strictement supérieurs à 1 (10 ≤ N ≤ 45).
Trier dans l’ordre croissant les éléments premiers sûrs du tableau T
suivis du reste deséléments sans tri.
Afficher le tableau T résultant.
Exercice 5 :
Écrire un programme Python qui permet :
- De remplir un tableau T par n entiers saisis dans un ordre croissant (4 ≤ n ≤ 10)
- De saisir un entier E et de l’insérer dans le tableau T à la bonne place de sorte que T
reste Trié.
- Afficher le tableau T résultant.
Exercice 6 :
Écrire un programme qui permet de saisir dans un tableau T1 N (6 ≤ N ≤20), Prénoms puis
remplir aléatoirement dans un tableau T2 par leurs couleurs {B pour les blancs, N pour les
Noirs} puis les trier de telle façon que les noirs avant les blancs et les prénoms soient trier
par ordres décroissant :
Ex : pour n =6 et
Exercice 7 :
Écrire un programme qui permet de saisie une phrase Ph décrivant les achats d’un élève
puis la trier (deux mots sont séparés par un espace, entre les achats il existe une virgule,
avant le dernieron trouve ʺetʺ)
Ex : si PH = ʺSami a acheté 10 cahier, 4 livres, 12 stylos . ʺ
Devient ʺSami a acheté 4 livres, 10 cahiers, 12 stylos .ʺ
45
46
47
