Algorithmes de tri

Fermé
NABLA93 - 18 avril 2010 à 20:21
 NABLA93 - 21 avril 2010 à 14:58
Bonjour à tous,

Alors voilà, j'ai un devoir à faire en info sur lequel je galère un peu.
J'ai trois tris à faire: un tri selection, un tri insertion et un tri à bulle.
Pour la programmation générale, je n'ai pas de problème mais on me demande d'y insérer un test booléen et ça, je n'y arrive pas.
Si quelqu'un peut m'aider, je l'en remercie.


3 réponses

Pacorabanix Messages postés 3248 Date d'inscription jeudi 23 août 2007 Statut Membre Dernière intervention 19 mai 2013 661
18 avril 2010 à 22:20
ce n'est pas très clair, mais je suppose qu'on te demande de faire en sorte que ton programme teste lui-même si le tableau est correctement trié, non ? histoire de vérifier automatiquement le résultat de ton code.
0
Et bien, si je prend l'exemple du tri selection, je te cite l'énoncé:
Ecrire tri_selection : ( 'a -> 'a -> bool) -> 'a vect -> 'a vect = <fun>
Cette fonction recherche le plus petit élément d'un vecteur v et le met en tête du vecteur puis elle recommence sur le vecteur privé de son premier élément et ainsi de suite...
On utilisera deux fonctions auxilliaires : echange i j v qui permute deux coordonnées et une seconde polymorphe minimum order a b v dui détermine le minimum d'un vecteur entre deux indices a et b.
echange : int -> int -> 'a vect -> 'a vect = <fun>
minimum : ('a -> 'a -> bool) -> int -> int -> 'a vect -> 'a vect =<fun>

J'ai réussi à trouver la fonction echange mais je n'arrive pas à trouve minimum.

Merci de ton aide.
0
Pacorabanix Messages postés 3248 Date d'inscription jeudi 23 août 2007 Statut Membre Dernière intervention 19 mai 2013 661
18 avril 2010 à 23:33
arf je n'ai aucune idée du langage que tu utilises, je ne peux pas t'aider, désolé.
0
C'est du Caml. Langage très scolaire qui pour moi ne présente pas vraiment d'intérêt.
En tout cas, je te remercie et je vais poursuivre mes recherches.
0
Logiquement, si on veut déterminer le minimum, on doit prendre ce que t'as appelé croissantSouple, non? Mais je ne vois pas comment on peut l'intégrer dans le tri ni quel est son but.
0
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 020
21 avril 2010 à 14:42
Je pense comprendre ce qu'on te demande...
Le ('a -> 'a -> bool) est une fonction a passer en paramètre qui permet de savoir comment tu dois comparer deux éléments de type 'a

Par ordre croissant ou décroissant, strict :
let croissantStrict x y = x<y;;
let decroissantStrict x y = x>y;;
let croissantSouple x y = x<=y;;
let decroissantSouple x y = x>=y;;

Ça te permet également de définir ton propre type 'a et ta propre fonction de comparaison.
Par exemple, si tu veux faire des arbres, tu devras définir ta propre fonction (plus ou moins efficace) de parcours d'arbre qui permette de comparer deux arbres. Et c'est avec cette méthode que tu pourras ensuite le trier.
0