Tri d'une liste dans le schéma

Question

Comment écrire un algorithme de tri qui retourne une liste dans l'ordre croissant.

ex: '(1 3 5 2 9) renvoie' (1 2 3 5 9)

Answer 1

SRFI 95 fournit une bibliothèque de tri. De nombreuses implémentations de Scheme ont également des bibliothèques de tri intégrées, bien qu'elles ne soient pas toutes conformes à l'interface SRFI 95.

---

Si vous devez écrire votre propre implémentation (pour les devoirs, par exemple), vous devez utiliser l'un des algorithmes de tri standard comme mergesort ou quicksort. Cependant, ces deux algorithmes sont des algorithmes basés sur des vecteurs, vous devrez donc copier la liste dans un vecteur, la trier, puis la recopier dans une liste. (Vous pouvez trouver SRFI 43 utile pour les opérations de manipulation de vecteurs, en particulier vector-swap! pour échanger deux éléments d'un vecteur.)

Il peut y avoir des algorithmes qui conviennent pour trier directement une liste chaînée. Je ne suis pas au courant avec eux, donc je ne commenterai pas sur eux plus loin.

Answer 2

La plupart des implémentations de schéma sont accompagnées d'une procédure de tri des listes. Si votre implémentation n'en fournit pas, il n'est pas difficile d'en lancer une. Voici une implémentation de l'algorithme de tri rapide:

> (define (qsort e) 
    (if (or (null? e) (<= (length e) 1)) e 
     (let loop ((left null) (right null) 
        (pivot (car e)) (rest (cdr e))) 
      (if (null? rest) 
       (append (append (qsort left) (list pivot)) (qsort right)) 
       (if (<= (car rest) pivot) 
        (loop (append left (list (car rest))) right pivot (cdr rest)) 
        (loop left (append right (list (car rest))) pivot (cdr rest))))))) 
> (qsort '(1 3 5 2 9)) 
=> (1 2 3 5 9)