Buts

• Utilisation de tableaux unidimensionnels.
• Implémentations d’algorithmes de tris.
• Manipulation de pointeurs de tableaux.

Énoncé

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. Nous avons déjà vu l’algorithme du tri par sélection. Les algorithmes des tris par fusion et par base sont décrits ci-dessous. Pour vous aider, on vous fournit un squelette que vous devez compléter.

Ce squelette (à télécharger ici) contient:

1. Une fonction main() qui lit au clavier la graine (seed), la taille du tableau (size) et le numéro de l’algorithme de tri (sorting_algo_number), génère un tableau aléatoire de valeurs entre -50 et 50, puis appelle l’algorithme de tri choisi.
2. Les signatures des fonctions des divers tris radix_sort(), merge_sort() et selection_sort(). Ces fonctions prennent en argument la taille d’un tableau et le tableau lui-même, et modifient le tableau durant leur exécution.
3. La fonction d’affichage des tableaux print() et la signature de la fonction is_sorted(), qui doit vérifier si le tri a réussi.

Vous aurez plusieurs tâches.

1. Écrire la fonction is_sorted() permettant de vérifier si le tri a réussi.
2. Écrire le code C correspondant au tri par fusion et au tri par base.
3. Découper vos tris en fonctions auxiliaires (fusion de deux sous-tableaux, lecture d’un bit, échange de pointeurs, copie de tableau, …).
4. En option, ajouter le tri par sélection.

Description des tris par fusion et par base

Tri par fusion (merge sort)

Le tri par fusion (en anglais, merge sort) est un tri par comparaison. Il s’appuie sur l’opération de fusion qui produit une liste triée à partir de deux listes triées. Ce tri procède itérativement en triant d’abord les paires de nombres, puis les groupes de 4 nombres, ensuite de 8, et ainsi de suite jusqu’à obtenir un tableau trié. À noter qu’il faut faire attention au cas général où le nombre d’éléments n’est pas une puissance de 2.

Pour son implémentation, le tri par fusion nécessite d’utiliser une zone temporaire de stockage des données de taille égale à celle de la liste de nombres à trier. On considère le cas du tri d’une liste de nombres entiers stockés dans un tableau.

Principe de l’algorithme

Soit size la taille du tableau à trier.

• Pour l’étape i = 0 à ⌈log₂(size)⌉ − 1, on répète:
  • Appliquer l’opération de fusion aux paires de sous-tableaux successifs de taille 2ⁱ (ou moins pour l’extrémité)

À noter qu’au début de l’étape i, les sous-tableaux de taille 2ⁱ sont triés et que la dernière paire de sous-tableaux peut être incomplète : le premier sous-tableau peut avoir moins de 2ⁱ éléments, et le second peut être plus court, voire vide.

La fonction de fusion (merge) produit à partir de deux tableaux triés, un 3ème tableau trié qui contient les éléments de ces deux tableaux. Si un des tableaux est vide, le résultat de la fusion est identique à l’autre tableau.

Elle procède de la manière suivante:

• Parcourir simultanément les deux tableaux jusqu’à atteindre la fin de l’un des deux
  • Comparer l’élément courant des deux tableaux
  • Écrire le plus petit élément dans le tableau résultat
  • Avancer d’une case dans le tableau d’où provient cet élément, ainsi que dans le tableau résultat
• Copier les éléments restants de l’autre tableau dans le tableau résultat

En pratique, à chaque étape, on fusionne les sous-tableaux du tableau à trier dans le tableau temporaire, puis on échange les rôles des deux tableaux pour l’étape suivante (voir les remarques à la fin de l’énoncé). Attention : les éléments du dernier sous-tableau, même s’il n’a pas de partenaire, doivent eux aussi être recopiés dans le tableau temporaire, sinon ils seront perdus lors de l’échange.

Illustration sur un exemple

Soit la liste de nombres entiers stockés dans un tableau de taille 9:

0. On fusionne les éléments successifs (ce qui revient à les mettre dans l’ordre) et on obtient:

1. On fusionne les paires successives (sous-tableaux de taille 2) et on a:

2. On fusionne les sous-tableaux successifs de taille 4 et on a:

3. On fusionne les sous-tableaux successifs de taille 8 et on obtient le résultat final:

Complexité

L’algorithme présenté précédemment nécessite un certain nombre d’opérations lié à la taille N du tableau.

Il y a ⌈log₂(N)⌉ étapes.

À chaque étape, le tableau est parcouru une fois avec un nombre constant d’opérations effectuées pour chacune des cases du tableau. En effet, l’opération de fusion implique de ne parcourir qu’une seule fois chacun des deux tableaux qu’on fusionne dans un 3ème tableau.

Ainsi, la complexité du tri par fusion est 𝒪(N ⋅ log₂(N)).

Tri par base (radix sort)

Le tri par base (en anglais, radix sort) est un tri qui n’utilise pas la notion de comparaison, mais celle de classement successif dans des alvéoles (buckets).

On considère le cas du tri d’une liste de nombres entiers stockés dans un tableau. Dans un premier temps, on applique un décalage aux éléments de la liste pour se ramener au cas où le plus petit élément est 0. On considère ensuite la représentation binaire de ces nombres. On numérote les bits à partir de 0 pour le bit de poids faible (le bit le plus à droite).

Principe de l’algorithme

1. On considère le bit le moins significatif (bit 0).
2. On parcourt une 1ère fois le tableau et on place à la suite dans un 2ème tableau les éléments dont le bit courant est à 0 ; puis on reparcourt le tableau une deuxième fois et on met à la suite les éléments dont le bit courant est à 1 (le 2ème tableau contient donc d’abord tous les éléments dont le bit courant est à 0, puis tous ceux dont il est à 1).
3. On répète l’étape 2 en regardant le bit suivant et en permutant le rôle des deux tableaux.

On utilise donc deux tableaux pour réaliser ce tri. À noter qu’à chaque étape, l’ordre des éléments dont le bit est à 0 (respectivement à 1) reste identique dans le 2ème tableau par rapport au 1er tableau.

Illustration sur un exemple

Soit la liste de nombres entiers:

Le plus petit élément est -9. On commence donc par décaler les valeurs de 9.

Écrivons à présent les éléments en représentation binaire. Comme la valeur maximale est 15, on a besoin de 4 bits.

On applique à présent l’algorithme (dans chaque tableau, le bit en gras est celui qui sera considéré à l’étape suivante).

1. On considère le bit de poids faible et on obtient le tableau:

   0	1	2	3	4	5	6	7	8
   1110	0100	1010	0000	1111	1101	0011	1011	1011

2. On passe au 2ème bit et on obtient le tableau:

   0	1	2	3	4	5	6	7	8
   0100	0000	1101	1110	1010	1111	0011	1011	1011

3. On passe au 3ème bit et on obtient le tableau:

   0	1	2	3	4	5	6	7	8
   0000	1010	0011	1011	1011	0100	1101	1110	1111

4. On passe au dernier bit et on obtient le tableau final:

   0	1	2	3	4	5	6	7	8
   0000	0011	0100	1010	1011	1011	1101	1110	1111

En revenant à la représentation décimale, on a le tableau trié:

Pour revenir aux valeurs initiales, il faut décaler de 9 dans l’autre sens.

Complexité

L’algorithme présenté précédemment nécessite un certain nombre d’opérations lié à la taille du tableau.

Voici une liste de parcours utilitaires de tableau:

1. Recherche de la valeur minimum val_min
2. Recherche de la valeur maximum val_max
3. Décalage des valeurs dans l’intervalle 0..val_max-val_min
4. Décalage inverse pour revenir dans l’intervalle val_min..val_max
5. Copie éventuelle du tableau temporaire dans le tableau originel

On a donc un nombre de parcours fixe (4 ou 5) qui se font en 𝒪(N) où N est la taille du tableau.

La partie du tri à proprement parler est une boucle sur le nombre de bits b nécessaires pour représenter val_max-val_min (si toutes les valeurs sont égales, on a b = 0 et il n’y a rien à trier).

À chaque passage dans la boucle, on parcourt 2 fois le tableau : la 1ère fois pour s’occuper des éléments dont le bit courant est à 0 ; la 2ème pour ceux dont le bit courant est à 1.

À noter que la lecture d’un bit et l’échange des pointeurs de tableaux se font en un nombre constant d’opérations.

Ainsi, la complexité du tri par base est 𝒪(b ⋅ N).

Remarques

Le 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 (avec k = 0 pour le bit de poids faible). 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 ET bit à bit (&) avec 1 (on fait un masque). Ainsi, pour un nombre sur 4 bits :

n = 13                // 1101 en binaire
k = 2
n >> k      == 0011   // 3 en décimal
0011 & 0001 == 0001   // soit 1 en décimal

L’échange de tableaux statiques

Pour certains tris à implémenter, vous devrez é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};
swap(&a, &b);
// 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. Or 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é en pointeur. Mais cela ne suffit pas.

L’impossibilité de faire un échange de tableaux statiques est due à 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. Or, échanger a et b reviendrait justement à écrire quelque chose comme a = b.

Pour pouvoir effectuer le travail qui vous est demandé, il faut soit faire de l’allocation dynamique (ce qu’on n’a pas encore fait en cours), soit 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), et une fonction qui échange deux pointeurs :

void swap_ptr(int **a, int **b) {
    int *tmp = *a;
    *a = *b;
    *b = tmp;
}

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;
swap_ptr(&c, &d);
// 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é. Au lieu de faire l’implémentation ci-dessus, vous pouvez échanger les valeurs se trouvant à l’intérieur 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.

Il suffit alors de parcourir les tableaux et d’échanger élément par élément

int a[] = {1, 2, 3, 4};
int b[] = {5, 6, 7, 8};
for (int i = 0; i < 4; ++i) {
    swap(&a[i], &b[i]);
}

où les éléments des tableaux sont ainsi échangés: a == {5, 6, 7, 8} et b == {1, 2, 3, 4}.

La copie du tableau final

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) {
        tmp[i] = 2 * tab[i];
    }
}
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) {
        times_two(size, tab_ptr, tmp_ptr);
        swap_ptr(&tab_ptr, &tmp_ptr);
    }
}
int main() {
    int a[] = {1, 2, 3, 4};
    do_things(4, a);
}

on pourrait se dire que a contiendrait {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 vers a, et il n’est jamais modifié : seuls les pointeurs locaux tab_ptr et tmp_ptr sont échangés, et ils sont détruits à la fin de do_things(). Ainsi, comme on échange trois fois les pointeurs, on ne modifie qu’une seule fois les données de a (à la 2ème itération) ; la valeur contenue dans a sera ainsi {4, 8, 12, 16}, alors que le résultat {8, 16, 24, 32} se trouve dans tmp. 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 n’aurait pas besoin de faire de copie car la dernière modification serait 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) {
        times_two(size, tab_ptr, tmp_ptr);
        swap_ptr(&tab_ptr, &tmp_ptr);
    }
    if (/* trouver la bonne condition */) {
        copy(size, tmp, tab); // copier les valeurs de tmp (source) dans tab (destination)
    }
}

Taille des tableaux

Les tableaux res (dans main()) et tmp (dans vos tris) sont alloués sur la pile, dont la taille est limitée (typiquement quelques mégaoctets). Pour des tableaux trop grands (de l’ordre du million d’éléments), votre programme plantera avec une segmentation fault. Testez donc vos tris avec des tailles raisonnables.