94
3 Arbres, algorithmes et données
rapide binaire (binary quicksort) [231] car il utilise un principe récursif analogue à
celui du tri rapide. Au lieu de choisir un pivot et de calculer la partition du tableau
en fonction de ce pivot, nous parcourons les données du tableau en examinant le
premier bit. Le but est d’avoir, après l’étape de partitionnement, tous les éléments
commençant par un 0 à gauche du tableau et, à droite, tous ceux débutant par 1. Pour
ce faire nous parcourons le tableau à l’aide de deux pointeurs. Le premier pointeur
parcourt le tableau de gauche à droite et recherche la première clé qui débute par 1.
Le deuxième pointeur parcourt le tableau de droite à gauche pour repérer la première
clé débutant par un 0. Les deux clés pointées sont alors échangées et le processus
se poursuit jusqu’à ce que les pointeurs se croisent. La partition est alors effectuée.
L’algorithme s’applique ensuite récursivement sur chacun des deux sous-tableaux
en passant au deuxième symbole, etc.
La procédure de partitionnement nécessite n comparaisons de bits. Notons que
les algorithmes de tri radix travaillent le plus souvent avec des références ou
des pointeurs vers les chaînes qu’ils manipulent. Ainsi lors du partitionnement
l’échange de deux clés correspond à échanger deux pointeurs et non pas les chaînes
en entier.
L’exécution de cet algorithme peut se lire sur un trie binaire puisque les appels
récursifs correspondent à choisir une branche dans le trie. Le nombre d’appels
récursifs est la taille du trie correspondant aux données (i.e., le nombre de nœuds
internes). Le nombre de fois où une clé est examinée (c’est-à-dire avec accès à un
de ses symboles) est égal à la profondeur de la feuille correspondante, et le nombre
total de symboles examinés est égal à la longueur de cheminement externe du trie.
Tri radix MSD Ici le terme MSD est l’acronyme de Most Significant Digits. Cela
signifie que les clés sont examinées de la gauche vers la droite, en examinant les
préfixes de longueur croissante des clés pour les trier. L’alphabet est de taille k et
pour k > 2, il s’agit d’une généralisation du cas précédent binaire. Une différence
essentielle concerne la procédure de partitionnement des chaînes selon leur premier
caractère. Cette partition en k ensembles (dont certains sont éventuellement vides)
correspondant aux k lettres de l’alphabet est effectuée à l’aide d’une méthode de tri
par comptage en temps O(k) (une présentation rapide du tri par comptage se trouve
en section A.5.6).
Tri radix LSD L’acronyme LSD Least Significant Digits signifie que nous allons
examiner les clés de la droite vers la gauche. Cette méthode suppose que toutes les
clés sont de même longueur. L’idée est assez contre-intuitive et consiste à trier les
données en commençant par les symboles de la fin. Pour que cela fonctionne, nous
avons absolument besoin d’utiliser une méthode de tri stable sur les symboles. Un tri
est stable si l’ordre des éléments est conservé lorsqu’il y a des données dupliquées.
Le tri par comptage constitue bien une méthode stable de tri. Ainsi le tri radix
LSD peut trier n mots de taille sur un alphabet de taille k en passes en partant
des symboles à la position − 1, puis − 2, . . . , 0. Une passe se fait par un tri par
comptage en O(n) en utilisant un espace auxiliaire de taille O(k).
3 Arbres, algorithmes et données
rapide binaire (binary quicksort) [231] car il utilise un principe récursif analogue à
celui du tri rapide. Au lieu de choisir un pivot et de calculer la partition du tableau
en fonction de ce pivot, nous parcourons les données du tableau en examinant le
premier bit. Le but est d’avoir, après l’étape de partitionnement, tous les éléments
commençant par un 0 à gauche du tableau et, à droite, tous ceux débutant par 1. Pour
ce faire nous parcourons le tableau à l’aide de deux pointeurs. Le premier pointeur
parcourt le tableau de gauche à droite et recherche la première clé qui débute par 1.
Le deuxième pointeur parcourt le tableau de droite à gauche pour repérer la première
clé débutant par un 0. Les deux clés pointées sont alors échangées et le processus
se poursuit jusqu’à ce que les pointeurs se croisent. La partition est alors effectuée.
L’algorithme s’applique ensuite récursivement sur chacun des deux sous-tableaux
en passant au deuxième symbole, etc.
La procédure de partitionnement nécessite n comparaisons de bits. Notons que
les algorithmes de tri radix travaillent le plus souvent avec des références ou
des pointeurs vers les chaînes qu’ils manipulent. Ainsi lors du partitionnement
l’échange de deux clés correspond à échanger deux pointeurs et non pas les chaînes
en entier.
L’exécution de cet algorithme peut se lire sur un trie binaire puisque les appels
récursifs correspondent à choisir une branche dans le trie. Le nombre d’appels
récursifs est la taille du trie correspondant aux données (i.e., le nombre de nœuds
internes). Le nombre de fois où une clé est examinée (c’est-à-dire avec accès à un
de ses symboles) est égal à la profondeur de la feuille correspondante, et le nombre
total de symboles examinés est égal à la longueur de cheminement externe du trie.
Tri radix MSD Ici le terme MSD est l’acronyme de Most Significant Digits. Cela
signifie que les clés sont examinées de la gauche vers la droite, en examinant les
préfixes de longueur croissante des clés pour les trier. L’alphabet est de taille k et
pour k > 2, il s’agit d’une généralisation du cas précédent binaire. Une différence
essentielle concerne la procédure de partitionnement des chaînes selon leur premier
caractère. Cette partition en k ensembles (dont certains sont éventuellement vides)
correspondant aux k lettres de l’alphabet est effectuée à l’aide d’une méthode de tri
par comptage en temps O(k) (une présentation rapide du tri par comptage se trouve
en section A.5.6).
Tri radix LSD L’acronyme LSD Least Significant Digits signifie que nous allons
examiner les clés de la droite vers la gauche. Cette méthode suppose que toutes les
clés sont de même longueur. L’idée est assez contre-intuitive et consiste à trier les
données en commençant par les symboles de la fin. Pour que cela fonctionne, nous
avons absolument besoin d’utiliser une méthode de tri stable sur les symboles. Un tri
est stable si l’ordre des éléments est conservé lorsqu’il y a des données dupliquées.
Le tri par comptage constitue bien une méthode stable de tri. Ainsi le tri radix
LSD peut trier n mots de taille sur un alphabet de taille k en passes en partant
des symboles à la position − 1, puis − 2, . . . , 0. Une passe se fait par un tri par
comptage en O(n) en utilisant un espace auxiliaire de taille O(k).