TD-1, tris élémentaires
Compte-rendu Nom.Prenom à déposer par CuteFtp sur poly en /users/profs/maranget/TD-1.
1 Tri élémentaire
Choisir un des tris élémentaires (sélection, bulle ou insertion) et le
programmer.
On triera un tableau d'entier t à NMAX éléments,
initialisés à des valeurs aléatoires comprises entre zéro et KMAX. C'est à dire que votre programme pourra commencer comme suit :
#include <stdio.h> /* comme d'habitude */
#include <stdlib.h> /* contient la définition de random */
#define NMAX ... /* taille du tableau */
#define KMAX ... /* plus grand élément possible */
int t[NMAX];
void initialiser(void)
{
int i;
for (i = 0 ; i < NMAX ; i++) {
t[i] = random(KMAX+1);
}
}
.....
2 Tri d'un tableau de chaînes
Trier la liste des élèves de la promo. Cette liste est disponible en
promo.txt, comme un tableau de chaînes
de la forme :
char *promo[] = {
"Chandon Cedric",
"Oblin Gabriel",
....
"Pinguet Benoit",
"Raynaud Elisabeth",
""
};
Le source ci-dessus est la déclaration et l'initialisation d'un
tableau d'objets de type char * (le
type des chaînes en C). Les chaînes peuvent être vues comme des
tableaux de caractères de taille variable. La fin d'une chaîne est
signalée par le caractère '\0'
. Une chaîne vide est donc un
tableau de caractères s, tel que s[0] == '\0'
.
La taille du tableau promo n'est pas
donnée (le compilateur la déduit de la liste de valeurs). Du point de
vue du programmeur, la fin du tableau est signalée par la chaîne vide
finale. Ainsi, par exemple, la fonction suivante affiche la liste des
élèves de la promo :
void affiche_promo(void)
{
int i;
i = 0;
while (promo[i][0] != '\0') {
printf("%s\n",promo[i]);
i++;
}
}
On demande de trier les élèves de la promo selon l'ordre du
dictionnaire. Dans un premier temps, on écrira une fonction inferieur, telle que, si s1 et s2 sont des chaînes,
inferieur(s1,s2)
, renvoie 0 (false
en C), si et
seulement si s1 ne précède pas s2 dans l'ordre
du dictionnaire. Le type de inferieur est le suivant :
int inferieur(char *s1,char *s2)
(Note : en C, on peut comparer les caractères à l'aides des opérateurs
usuels et leur ordre est compatible avec l'ordre alphabétique.)
Ensuite on utilisera un des algorithmes de tri élémentaires, puis on
affichera la liste triée sur la console. On aura sans doute intérêt à
faire quelques essais avec une liste raccourcie.
Enfin, on pourra ranger la liste triée des élèves dans un fichier. Pour
ce faire :
-
Lancer Commandes MS-DOS dans le menu Démarrer...Programmes
- Se positionner dans le répertoire de travail où vous avez
compilé votre programme (par exemple promo.exe, dans C:\Td\Td-1), par la commande MS-DOS cd (dans
notre exemple : cd C:\Td\Td-1).
- Lancer promo.exe avec sortie redirigée vers un fichier :
promo.exe > coucou.txt.
- Fermer (éventuellement) la fenêtre MS-DOS (commande exit
ou croix en haut à droite).
Si votre programme est correct, la liste triée est maintenant dans le
fichier coucou.txt que vous pouvez examiner avec le Bloc Notes. On peut aussi visualiser le fichier coucou.txt sous
MS-DOS, par type coucou.txt, more coucou.txt ou edit
coucou.txt.
3 ``Counting sort''
On considère le cas d'un tableau t, de NMAX entiers compris entre
zéro et KMAX, comme dans le premier exercice.
On définit un nouveau tableau c de taille k+1, tel que
c[i]
est le nombre des éléments de t qui sont plus petits
ou égaux à i. Écrire un programme qui initialise le tableau c, puis utilise c pour ranger une copie triée de t dans
un tableau résultat r. Pour trouver l'inspiration, on pourra
d'abord considérer le cas où tous les entiers de t sont distincts.
Estimer le coût asymptotique de cette procédure de tri, en fonction de
n et de k.
4 S'il vous reste du temps
Vous trouverez en selection.txt, un programme qui fait une
démonstration graphique du tri par sélection en affichant tous les états
intermédiaires du tri par sélection dans une fenêtre graphique.
Ce programme utilise la MacLib. Donc, il faudra d'abord récupérer
maclib.lib et maclib.h par CuteFtp, sur poly
dans le répertoire /users/profs/maranget/maclib et les installer
respectivement
dans C:\Bc5\Lib et C:\Bc5\Include.
En cas d'échec, me demander une disquette. En cas d'échec, recompiler
la MacLib, à partir des sources
Ensuite, compiler le programme, l'exécuter et le comprendre
suffisamment pour pouvoire changer le tri sélection en tri à bulles,
par exemple.
Ce document a été traduit de LATEX par
HEVEA.