La complexité des
algorithmes
Auteur : Seb/the Removers
La complexité des algorithmes
La compression fractale
Auteur : Stabylo/the Removers
La compression fractale
Le tri rapide
Auteur : Seb/the Removers
Le Quick Sort (ou tri rapide pour les anglophobes) est une des meilleures solutions pour trier des données. 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
ap dans un tableau
a=(a0,...,an) (n entiers positifs),
alors récursivement, nous pourrions trier les sous
tableaux (a0,...,ap-1) et
(ap+1,...,an) : voilà ce que
l'on appelle le quick sort !
Il nous faut donc savoir
créer un pivot dans un tableau
a=(ag,...,ad) :
let cherche_pivot a g d =
let ob=a.(g) and i=ref g in
for j=g+1 to d do
if ob>a.(j) then (incr i;echange a !i j)
done;
echange a g !i;
!i;;
où la fonction echange se charge
d'échanger deux éléments d'un
tableau.
let qsort a =
let rec qs g d =
if d-g>1 then
(
let i=cherche_pivot a g d
in qs g (i-1);
qs (i+1) d
)
in qs 0 (vect_length a - 1);;
En assembleur 68020 !
Niveau
complexité, on peut prouver que la complexité en
moyenne du tri rapide est en O(n*log(n)), j'ai le
détail dans mes cours si cela vous
intéresse !
Les formats des modules MOD, MTM, MGT, 669 et XM
Auteur : Simplet/Fatal Design
Le format MOD (ASCII)
Le format MTM (ASCII)
Le format MGT (ASCII)
Le format 669 (ASCII)
Le format XM
Auteur : Mr.H/Triton
Le format XM (ASCII)
Le format GT2
Auteur : L. de Soras
Le format GT2 (ASCII)
[Entrée du site] [Presentation du groupe] [Nos articles] [Nos logiciels] [Téléchargement] [Nos liens] [Contacts] [Nouveautés du site]
[Main page] [Presentation of the group] [Our products] [Download] [Links] [Contacts] [What's new]
