Tri des Tableaux
Exercice 1
Une station de radio lance chaque début de semaine un concours hebdomadaire intitulé
"Hitparade" pour classer cinq titres de chansons qu'elle propose à ses auditeurs et affiche le
résultat du classement le samedi. Tout au long de la semaine, un responsable de la station reçoit
par téléphone les propositions des participants au concours parmi ses auditeurs qui sont appelés
à choisir le titre préféré afin d'ajouter à son score 3 points. Pour obtenir le classement final des
cinq chansons suite à la participation d'un nombre donné des auditeurs de la station, on se
propose d'écrire un programme qui permet de :
• Remplir un tableau T1 par les cinq titres des chansons, sachant qu'un titre est composé
uniquement par des lettres alphabétiques et des espaces.
• Saisir le nombre N de participants avec 5 <=N <= 100.
• Générer un tableau T2 représentant les scores des cinq chansons en ajoutant 3 points au
score de chacune si le numéro qui lui correspond a été choisi par un participant. Ce
numéro est un chiffre allant de 1 à 5, représentant l'emplacement de la chanson dans le
tableau T1.
• Afficher le classement des chansons, comme indiqué dans l'exemple ci-après, en
commençant par le titre de la chanson ayant le plus grand score. Il est à noter que les
chansons ayant un même score auront un même rang dans le classement.
Exemple :
Pour :
T1 Happy Sorry Me Quemo Rosa Hello
0 1 2 3 4
Et un nombre de participants N = 11 ayant fait les choix suivants :
Choix du participant n°1: 5 Choix du participant n°5 : 2 Choix du participant n°9 : 4
Choix du participant n°2: 4 Choix du participant n°6 : 5 Choix du participant n°10 : 1
Choix du participant n°3 : 5 Choix du participant n°7 : 1 Choix du participant n°11 :5
Choix du participant n°4 : 1 Choix du participant n°8 : 2
On aura
T2 9 6 0 6 12
0 1 2 3 4
Le programme affiche :
Le classement est : Rang 1 : Hello
Rang 2 : Happy
Rang 3 : Sorry, Rosa
Rang 4 : Me Quemo
FATEN BEN ALI
1
Exercice 2
Soit T un tableau de N entiers (avec 6SN<50). On se propose de trier le tableau T dans l'ordre
croissant en utilisant le principe suivant :
1. On parcourt le tableau T de gauche à droite en comparant les éléments de T deux à deux (T[i]
avec T[i+1]) et en les permutant si nécessaire. Le premier parcours permet de placer le plus
grand élément dans la dernière case.
2. On parcourt le tableau de droite à gauche (sans tenir compte de la dernière case : case triée)
tout en comparant chaque deux éléments consécutifs de T et en les permutant si nécessaire pour
placer le plus petit élément à sa bonne place (case n°0).
3. On refait les étapes 1 et 2 en parcourant le tableau tantôt de gauche à droite et tantôt de droite
à gauche sans tenir compte des cases triées. Le traitement sera arrêté lorsque le tableau est trié.
Exemple :
Soient N=6 et le tableau T suivant :
13 6 4 20 5 9
0 1 2 3 4 5
En appliquant le principe décrit ci-dessus sur le tableau T précédent, on obtient les étapes
suivantes :
1. Le 1er parcours de gauche à droite, permet de placer la valeur 20 (plus grand élément de T)
dans la case n°5.
6 4 13 5 9 20
0 1 2 3 4 5
2. Le 1er parcours de droite à gauche (sans tenir compte de T[5]), permet de placer la valeur 4
(plus petit élément de T) dans la case n°0.
4 6 5 13 9 20
0 1 2 3 4 5
3. Le 2ème parcours de gauche à droite (sans tenir compte de T[0] et T[5]) permet de placer la
valeur 13 (plus grand élément de la portion du tableau allant de la case 1 à la case 4) dans la
case n°4.
4 5 6 9 13 20
0 1 2 3 4 5
4. Durant le 2ème parcours de droite à gauche (de la case 3 à la case 1), aucune permutation n'a
été faite, donc le tableau est trié.
on se propose d’écrire un programme qui permet de remplir un tableau T par N entiers puis de
trier T selon le principe décrit précédemment et d’afficher le tableau trié.
FATEN BEN ALI
2
