Algorithmes de tri
NABLA93
-
NABLA93 -
NABLA93 -
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.
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.
A voir également:
- Algorithmes de tri
- Comment faire un tri personnalisé sur excel - Guide
- Logiciel tri photo - Guide
- Votre colis est retenu au centre de tri - Accueil - Arnaque
- Tri turf - Télécharger - Sport
- Google sheet tri automatique ✓ - Forum Bureautique
3 réponses
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.
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.
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.
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.
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.