Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
Programmation : Assembleur - Routine de tri
(Article écrit par Max et extrait d'Amiga News Tech - septembre 1990)
|
|
M. Sorant, de Vernouillet dans l'Eure-et-Loire, pose cette angoissante question : "je suis intéressé par une routine
de tri faisant suite à l'article en assembleur
sur la lecture du répertoire d'une disquette. Merci d'avance".
Mais comment donc, il suffit de demander. Il existe plusieurs algorithmes de tri, parmi lesquels on peut citer
les plus connus : le Bubble-Sort, le Quick-Sort ou encore le Heap-Sort. Chacun présente des avantages et des
inconvénients, qui ne seront pas discutés ici, on n'a pas que ça à faire. Dans notre cas, nous allons nous contenter
du Bubble-Sort, car c'est de loin le plus simple à programmer (la preuve : la routine ne fait que 13 lignes !).
La marche à suivre est simple : tous les éléments du tableau à trier sont traités à l'intérieur de deux boucles.
La première détermine le plus petit élément figurant entre un élément "N" et la fin du tableau, en le comparant
successivement à tous ceux qui sont derrière lui. Si l'un des éléments comparés s'avère être plus petit que "N",
on échange les deux et il devient le nouvel "N" jusqu'à la fin de la boucle. La seconde boucle fait en sorte que
la première soit exécutée pour chaque élément du tableau. Ce tri n'est certes pas le plus optimisé, et malgré
la vitesse du 68000, il faut plus de 20 secondes pour trier un tableau de 10 000 éléments.
Cela dit, pour de petits tableaux (jusqu'à 1000 éléments), le temps nécessaire reste inférieur à la seconde.
Mais trêve de bavardages, voici la routine. Elle attend dans a0, l'adresse du tableau à trier et dans d0,
le nombre d'éléments que contient le tableau.
Telle quelle, la routine trie un tableau de "words" (16 bits) dans l'ordre croissant, en tenant compte du
signe des éléments. Pour trier par ordre décroissant, il faut remplacer l'instruction de saut "ble" par "bge".
Pour ne plus tenir compte du signe, il faut la remplacer par "bcs" pour l'ordre croissant ou par "bcc"
pour l'ordre décroissant. L'adaptation à des tableaux de "bytes" (8 bits) et de "longs" (32 bits) est laissée
à votre sagacité...
Travail à la chaîne
Pour trier des chaînes de caractères, il faut procéder autrement. Le Bubble-Sort sera également utilisé,
mais ce ne seront pas les chaînes elles-mêmes qui seront triées, mais plutôt un tableau de pointeurs sur
ces chaînes. En effet, trier directement un tableau de chaînes ASCII relèverait plus de la folie furieuse
que de l'initiation à l'assembleur. Avec des pointeurs, tout devient plus facile.
La routine utilisée
ne présente pas énormément de différences avec la première. Simplement, elle fait appel à une seconde
routine chargée de comparer deux chaînes de caractères entre elles pour déterminer s'il faut ou non échanger
les deux pointeurs. Le reste est identique. Le petit programme suivant trie le tableau. Puis affiche le résultat.
Et voilà, ce n'est pas plus difficile que ça. L'adaptation à la routine de lecture de catalogue ne devrait
pas poser de problème particulier - enfin, j'espère.
|
