Procédure de tri dans le schéma

Question

Comment puis-je écrire ma propre procédure Trier dans un schéma qui prend une procédure et la trie en fonction de la procédure!

Si nous le pouvons, Quelle est la procédure?

exemple - (tri « (2 4 9 5 3)>) les rendements (9 5 4 3 2)

Et peut-on proposer une procédure de recherche chaque élément d'une liste dans une deuxième liste!

Answer 1

C'est assez simple. Vous venez de donner la variable de tenir le prédicat un nom et mettre en œuvre la stratégie de tri de vous aimer ..

;; implements a 2 element sort 
(define (my-sort2 lst <) 
    (let ((fst (car lst)) (snd (cadr lst))) 
    (if (< snd fst) 
     (list snd fst) 
     lst))) ; already in correct order 

(sort '(1 2) >) ; ==> (2 1) 
(sort '(1 2) <) ; ==> (1 2) 

Dans un savoir algorithme de tri un peu plus avancé que vous ne devez pas les deux (< snd fst) et (< fst scd) de telle sorte que dans le cas les deux sont ce sont faux, vous avez la troisième option qu'ils sont les mêmes.

Exécutez maintenant pour trouver the sorting algorithm que vous souhaitez implémenter. Pour quelques éléments même les bibliothèques professionnelles utilisent Insertion sort et souvent pour les plus grands ensembles de données merge sort or quick sort sont de bons choix.

De nombreux algorithmes de tri sont plus rapides s'ils sont effectués dans des vecteurs de taille fixe pour des listes plus longues. Ainsi, la plupart des bibliothèques créent d'abord un vecteur mutable avec les valeurs, fait le tri en place, puis le retourne dans une liste. Dans les implémentations Scheme comme DrRacket vous pouvez faire un clic droit sur leur sort et ouvrir le fichier de définition pour voir comment cela est fait. Inutile de dire que c'est assez avancé pour bien faire dans la plupart des cas.