Schéma trier une liste

Question

Bon, alors j'essaie de prendre une liste et de la trier du plus grand au plus petit.

Example: 
> (maxheap (list 5 6 2 1 18 7)) 
;output: 
> (18 7 6 5 2 1) 

Alors, voici ce que je suis arrivé à ce jour:

(define (mkmaxheap heaplist) 
    (let ((max (mymax(heaplist)))) 
    ;mymax is a func that returns max number, it works 

    (let ((head (car heaplist)) (tail (cdr heaplist))) 
     (if (null? tail) 
     newlist)))) 

C'est tout ce que je pouvais obtenir de compiler, tous les autres codes I Wrote a échoué. Toute aide pour résoudre ce problème serait très appréciée.

Answer 1

Vous devez articuler soigneusement la stratégie que vous souhaitez utiliser pour produire la liste triée. Est-ce quelque chose comme ça?

• Trouvez le nombre maximal dans la liste.
• Obtenez le reste de la liste, sauf pour le maximum.
• Triez le reste de la liste et placez le maximum sur le devant de la liste.

Ce n'est pas un moyen très rapide de le trier, mais cela devrait fonctionner. La prochaine étape de votre code sera d'écrire une fonction pour obtenir le reste de la liste, sauf pour le maximum (prenez soin de le gérer correctement si la liste a des doublons.)

Une fois que vous avez écrit cela, vous devriez être capable d'écrire le code Scheme qui ressemble plus ou moins au contour ci-dessus.

Answer 2

Il s'agit d'un algorithme de tri de fusion dans Common Lisp. Il est à peu près proche de l'implémentation du même type dans le schéma.

(defun merge-sort(input) 
    (labels ((right-half (input) 
      (last input (ceiling (/ (length input) 2)))) 
      (left-half (input) 
      (ldiff input (right-half input)))) 
    (if (or (null input) (null (cdr input))) 
     input 
     (merge 'list (merge-sort (left-half input)) (merge-sort (right-half input)) #'<)))) 

Answer 3

Vous devez décider ce qu'il faut utiliser pour trier la liste. J'ai récemment bricolé avec le système, en travaillant sur SICP et la série "Schemer", et j'ai trouvé qu'il était très facile d'implémenter un tri à bulles, un tri par fusion et un tri rapide.

Answer 4

Vous n'avez pas spécifié l'implémentation que vous utilisez. Mais il peut implémenter r6rs list-sort ou srfi-95 sort ou tout autre tri intégré. Consultez la documentation de votre implémentation.