Le tri baquet

Notion utilisée

Les listes chaînées

Cahier des charges

k étant un entier donné, il s'agit de trier avec le "tri baquet"des entiers positifs ou nuls ayant au plus k chiffres. Le fichier donnees.dat contient :

la valeur de k
les entiers à trier

La liste triée sera mise dans le fichier resultats.dat

Le tri baquet

On suppose que les données positives ou nulles sont écrites en écriture décimale avec au plus k chiffres, autrement dit que les données sont inférieures à 10 puissance k.

On utilise un tableau, dit tableau de "baquets", indicé par 0, 1, ...., 9. Le tableau s'appelle baquet. Les baquets sont donc : baquet[0], ..., baquet[9]. Chacun des baquets est une structure contenant deux pointeurs destinés à contenir les adresses du début et de la fin d'une liste chaînée d'entiers, liste qui sera dite "contenue" par le baquet correspondant.

L'algorithme se déroule de la façon suivante :

On chaîne les données : soit L la liste obtenue.
Pour i qui varie de 1 à k :
- On initialise à "rien" toutes les adresses des baquets.
- On prend un à un les maillons de L. Pour chaque maillon m :
  - on note n la donnée contenue dans m
  - on note num le ième chiffre de n en partant de la droite (par exemple, si i vaut 1, num est le chiffre des unités de n)
  - on chaîne m à la fin de la liste chaînée contenue par baquet[num]. On actualise en conséquence les deux pointeurs de baquet[num].
- On reconstitue une liste L en chaînant "bout à bout" le contenu de baquet[0], puis de baquet[1], ..., puis de baquet[9].
On écrit le résultat dans le fichier resultats.dat.

Le travail à faire

Vous compléterez le programme exo_baquet.c.

Corrigé

Voir le corrigé .

Irène Charon

Last modified: Tue Sep 7 16:11:03 MET DST 1999