make
.L’objectif de ce travail pratique est d’implémenter les tris vus en cours. En particulier, vous devez écrire les codes en C des tris par base et par fusion, puis si le temps le permet le tri par sélection et le tri rapide. Les pseudo-codes de ces tris se trouve dans les slides du cours. Pour vous aider, on vous fournit un squelette que vous devez compléter.
Ce squelette (à télécharger ici) contient:
main()
qui lit la ligne de commande,
génère un tableau et permet de sélectionner son algorithme tri.radix_sort()
, merge_sort()
,
selection_sort()
, et quick_sort()
. Ces
fonctions prennent en argument un tableau et sa taille et modifie le
tableau durant leurs exécutions.print()
et la vérification si
le tri a réussi.Vous aurez plusieurs tâches.
Makefile
.size
, seed
,
sorting_algo_number
dans le code et lire la la ligne de
commande pour faire en sorte que le code compile et s’exécute.k
-ème bit d’un entier
n
Pour le tri par base, vous devez implémenter une fonction qui
retourne le k
-ème bit d’un nombre n
. Pour ce
faire, vous pouvez utiliser la syntaxe suivante:
(n >> k) & 1
où on commence par décaler tous les bits de n
de
k
bits vers la droite, puis on fait un
&
-logique bit à bit avec 1
(on fait un
masque). Ainsi pour un nombre 4
-bits
= 13 // 1101
n = 2
k >> k == 0011 // 3 en décimal
n 0011 & 0001 == 0001 // soit 1 en décimale
Certains tris à implémenter, vous devez échanger les pointeurs vers des tableaux statiques.
En effet, on pourrait se dire que le code suivant
int a[] = {1, 2, 3, 4};
int b[] = {5, 6, 7, 8};
(&a, &b);
swap// ici en fait a est toujours le tableau 1, 2, 3, 4
// et b est toujours 5, 6, 7, 8
ferait pointer le tableau a
sur les données de
b
et vice-versa. Hors ce n’est absolument pas le cas car
les tableaux statiques ne sont pas que des pointeurs.
Quand on passe un tableau statique en argument à une fonction, il est
effectivement transformé pointeur. Mais cela ne suffit pas.
L’impossibilité de faire un échange de tableaux statique est dûe à
l’impossibilité en C
d’assigner un tableau statique à un
autre tableau statique. Ainsi,
int a[3] = {1, 2, 3};
int b[3] = a;
n’est pas une syntaxe valide et c’est ce qu’on essaie de faire dans le code précédent.
Pour pouvoir effectuer le travail qui vous est demandé, il faut soit faire de l’allocation dynamique (ce qu’on a pas encore fait en cours) ou alors tricher un peu. En fait, pour réussir à faire un échange de pointeurs de mémoire, il faut définir deux nouvelles variables, qui sont des vrais pointeurs (elles). En transformant le code ci-dessus en
int a[] = {1, 2, 3, 4};
int b[] = {5, 6, 7, 8};
int *c = a;
int *d = b;
(&c, &d);
swap_ptr// ici en fait a est toujours le tableau 1, 2, 3, 4
// et b est toujours 5, 6, 7, 8
// mais c pointe sur 5, 6, 7, 8
// et d pointe sur 1, 2, 3, 4
on a l’effet voulu. On échange effectivement les pointeurs vers les données voulues.
Attention Si vous n’avez rien compris à ce qui précède, je ne suis pas choqué. Vous pouvez à la place de faire l’implémentation ci-dessus, faire un échange des valeurs se trouvant à l’intérieurs des tableaux plutôt que de tenter d’échanger des pointeurs. Cela ralentira un peu l’exécution, mais c’est quand même plus compréhensible.
Quand on échange les pointeurs vers des tableaux statiques dans la fonction de tri, un problème peut survenir. Prenons le code suivant très simple
void times_two(int size, int tab[], int tmp[]) {
for (int i = 0; i < size; ++i) {
[i] = 2 * tab[i];
tmp}
}
void do_things(int size, int tab[]) {
int *tab_ptr = tab;
int tmp[size];
int *tmp_ptr = tmp;
for (int i = 0; i < 3; ++i) {
(size, tab, tmp)
times_two(&tab_ptr, &tmp_ptr);
swap}
}
int size = 4;
int a[size] = {1, 2, 3, 4};
(size, a); do_things
on pourrait se dire que a
pointerait vers
{8, 16, 24, 32}
. Il n’en est rien. En effet, dans la
fonction do_things()
, le pointeur tab
n’est
qu’une copie du pointeur de a
. Ainsi, le
pointeur vers a
n’est jamais vraiment modifié, seul
tab
l’est et il est détruit à la fin de
do_things()
. Ainsi, comme on échange trois fois le
pointeur, on ne modifie qu’une seule fois les données qui sont pointées
par a
, la valeur contenue dans a
sera ainsi
{4, 8, 12, 16}
. Pour finir l’implémentation de la fonction,
il faut encore copier les données dans tab
si le besoin
s’en fait sentir (si on allait jusqu’à 4
dans la boucle
for
de do_things()
on aurait pas besoin de
faire de copie car la dernière modification est dans les données
pointées par a
).
void do_things(int size, int tab[]) {
int *tab_ptr = tab;
int tmp[size];
int *tmp_ptr = tmp;
for (int i = 0; i < 3; ++i) {
(size, tab, tmp)
times_two(&tab_ptr, &tmp_ptr);
swap}
if // trouver la bonne condition
{
(size, tmp, tab); // copier les valeur de tmp dans tab
copy}
}