TD-1, tris élémentaires

Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/X.97/TD-1/enonce.html

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 :
  1. Lancer Commandes MS-DOS dans le menu Démarrer...Programmes
  2. 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).
  3. Lancer promo.exe avec sortie redirigée vers un fichier : promo.exe > coucou.txt.
  4. 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
(cf. http://lix.polytechnique.fr/Labo/Philippe.Chassignet/MACLIB/Borland_C/maclib_bcw.html).

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.