Le tri rapide

Nous vous en proposons une traduction en assembleur 68020 pour trier un tableau de mots. Mais avant de commenter le source (qui l’est beaucoup plus qu’un de mes sources habituels !), faisons un peu de théorie !

Pour cela, commençons par un petit exemple. Soit le tableau : [26 18 4 9 37 119 63 220 47 74]. Le nombre 37 a un role très particulier : tous les objets avant 37 sont plus petits que 37 et tous ceux après 37 sont plus grands que 37. On donne le nom de pivot à un tel objet. Supposons maintenant que nous sachions trouver un pivot a_p dans un tableau a=(a₀,...,a_n) (n entiers positifs), alors récursivement, nous pourrions trier les sous tableaux (a₀,...,a_p-1) et (a_p+1,...,a_n) : voilà ce que l'on appelle le quick sort !
Il nous faut donc savoir créer un pivot dans un tableau a=(a_g,...,a_d) :

où la fonction echange se charge d’échanger deux éléments d’un tableau. La traduction du tri rapide est alors immédiate : Toujours en CAML :

Quicksort en assembleur 68020

Un exemple d’implémentation de l’algorithme du tri rapide en assembleur 68020.

En assembleur 68020 !