En un mot comme en mille : ce topic est un grand recueil indexant foule d'implémentations d'algorithmes. Ces algorithmes sont très divers, allant à toucher le domaine du tri jusqu'aux algorithmes de résolution d'équations en passant par les algorithmes de cryptage. Il y aura de tout, enfin, de tout ce que vous aurez à proposer ! Nous y reviendrons. Ce topic sera donc une titanesque base de données regroupant énormément d'algorithmes (principe, complexité, implémentation, etc. ; avec un algorithme présenté par post). Les algorithmes peuvent être implémentés dans un langage au choix, plusieurs c'est encore mieux ! L'intérêt de ce topic est multiple et bien évident : chaque programmeur pourra aller se servir en code sur ce topic-même sans devoir se soucier de problèmes d'implémentation qui ne l'intéressent pas forcément et qui ne font pas nécessairement l'objet de ses priorités. De plus, cela peut-être un lieu de découverte et d'enrichissement pour ceux qui découvrent le vaste et génial monde de l'algorithmique.
Le topic sera naturellement rigoureusement organisé. Chaque post ci-présent présentera un algorithme (nous y reviendrons aussi). Ce premier post fera office de post de référence et vous permettra d'accéder à la fiche de chaque algorithme indexé dans ce topic. Vous pouvez voir que, plus bas, j'ai prévu une division "Index" qui listera de manière claire les algorithmes présents sous la forme "nom_de_lalgo [Lang1] [Lang2]". nom_de_lalgo sera remplacé par le nom de l'algorithme et un lien y sera mis qui permettra d'accéder à la première fiche présentant l'algo en question. Les tags de langage seront des liens accédant aux posts qui présenteront l'algo en question dans le langage précisé. Le lien sur le nom de l'algo pourrait sembler inutile puisque si l'implémentation présentée est en Caml par exemple, il y aura un lien pointant sur le même post dans le tag [Caml]. Néanmoins, ce premier lien permettra d'accéder non pas uniquement à une implémentation mais au premier post parlant de cet algorithme qui sera donc accompagné d'une brève explication et d'au moins un lien vers une page plus détaillée.
We need you !
Comme vous l'avez deviné, le fonctionnement de cette banque de données est un peu comme celui des distributions linux : chacun peut y contribuer ! En d'autres termes, le contenu de ce grand topic sera le fruit de vos contributions et j'encourage toutes les personnes se croyant aptes à présenter correctement et sans faute un algorithme à poster leur présentation, ou si c'est déjà fait, une implémentation dans leur langage favori (et si là, c'est déjà fait, vous aurez d'autres occasions de contribuer au topic). Les contributeurs pourront donc poster deux types de posts que nous verrons dans l'ordre. Premièrement, les posts présentant un algorithme nouveau, ne figurant pas encore dans l'index du premier post. Comme c'est du nouveau, il faudra le présenter au moins brièvement et de manière structurée en parlant de tout ce qui vous semble nécessaire (principe, complexité (pire des cas, etc...), histoire (?), etc.). Vous pouvez ma foi aller jusqu'à faire un article très très détaillé si vous le souhaitez (et je vous y encourage ; mais je rappelle quand même que le but premier du topic est le code !). Dans tous les cas, il y aura une petite mise en forme pas très imposante à respecter (c'est pas évident de gérer quand c'est le bordel et que chacun présente tout différemment) :
<titre1><couleur nom="marine">Catégorie de l'algorithme : Nom de l'algorithme</couleur></titre1>
<titre2>Principe</titre2>
<titre2>Complexité</titre2>
<titre2>...</titre2>
<titre2>[Langage de l'implémentation] Implémentation</titre2>
Deuxièmement, les posts présentant une implémentation d'un algorithme déjà présenté mais dans un langage dans lequel il n'est pas encore implémenté. Là, je pense que le mieux est encore une présentation libre, expliquez quand même vos codes et dites clairement quelque part qu'il s'agit d'une implémentation dans un autre langage histoire de me simplifier la tâche pour éditer ce post :-°. Je vous remercie déjà d'avance pour vos contributions qui vont aider plus d'un ! Si vous souhaitez refondre un post, contactez de préférence le posteur par MP.
Enfin, il faut savoir que personne n'est parfait et il est donc tout à fait possible, comme chacun peut poster (il faut quand même qu'il maîtrise l'algorithme qu'il présente), que des erreurs se soient glissées dans les explications ou les codes donnés (euh et pour les codes, testez-les toujours avant de poster !). Si par hasard il devait arriver à quelqu'un de rencontrer une telle erreur, deux possibilités s'offrent à lui : soit ce n'est vraiment pas grand chose, auquel cas il poste directement dans ce topic en espérant que le souci sera réglé au plus vite, soit c'est plus gros et il devra, pour éviter les dérives trop importantes, poster un nouveau topic dans le forum approprié (un problème dans un code en C ? Go forum C, etc.) avec un titre assez explicite si possible.
Le tri fusion se base sur le fait que fusionner deux listes triées est en complexité linéaire O(n). Le principe, récursif, est défini de la manière suivante : on coupe la liste à trier en deux, on trie chaque moitié avec le tri fusion et on fusionne les deux parts. On stoppe les appels récursifs dès que l'on tombe sur une moitié vide ou un singleton, qui sont donc triés. Pour en savoir (beaucoup) plus, l'article wikipédia ici et une explication par bluestorm ici vous seront utiles.
Complexité
La complexité de ce tri est toujours en O(n log n).
[OCaml] Implémentation
Dans mon implémentation, j'utilise les listes chaînées en tant que structure de données à trier. Le code est structuré en trois fonctions et leur rôle est très clair : nous avons une fonction "fusion" qui prend en paramètre une paire de listes a,b (triées) et qui renvoie la liste résultat de la fusion de a avec b. La fonction "split" se charge de couper la liste passée en paramètre en deux parties dont la taille varie au plus d'un. Son intérêt devient crucial dans la fonction "tri_fusion" : cette fonction prend en paramètre une liste (la liste à trier), la coupe en deux parties égales avec la fonction "split" et trie chaque part avec "tri_fusion" avant d'appliquer la fonction "fusion" sur les deux moitiés alors triées.
let rec fusion = function
| ([], l) | (l, []) -> l
| (t1::q1, t2::q2) ->
if t1 < t2 then t1::fusion (q1, t2::q2)
else t2::fusion (t1::q1, q2)
let rec split a b = function
| [] -> (a, b) | [l] -> (l::a, b)
| t::n::q -> split (t::a) (n::b) q
let rec tri_fusion = function
| ([] | [_]) as l -> l
| l -> let a, b = split [] [] l in
fusion (tri_fusion a, tri_fusion b)
Euh, je veux pas venir foutre le bazar, mais ton code est bizarre. _asl-> : d'où tu sors ça ? Et puis c'est pas super cohérent, dans une fonction c'est curryfié et pas dans l'autre, tes pipes de filtrage sont pas décalés mais le reste si...
Sinon, l'idée du topic en soit est pas mauvaise, mais vu la diversité des langages et des algorithmes, je sais pas si ça vaut vraiment le coup... Personnellement si j'en cherche un, j'aurais plus tendance à aller sur wikipedia, en plus il sera a priori mieux expliqué et détaillé en une page qu'en quelques lignes.
C'est correct mais plus long qu'utile. Je corrige.
Citation : Maxibolt
Et puis c'est pas super cohérent, dans une fonction c'est curryfié et pas dans l'autre
C'est cohérent, j'ai à chaque fois pris la solution la plus courte / intuitive. Et puis, il n'y a aucun mal à ça.
Citation : Maxibolt
tes pipes de filtrage sont pas décalés mais le reste si...
C'est un style d'indentation et c'est celui que j'utilise toujours quand j'écris un code OCaml.
Citation : Maxibolt
Sinon, l'idée du topic en soit est pas mauvaise, mais vu la diversité des langages et des algorithmes, je sais pas si ça vaut vraiment le coup... Personnellement si j'en cherche un, j'aurais plus tendance à aller sur wikipedia, en plus il sera a priori mieux expliqué et détaillé en une page qu'en quelques lignes.
D'où l'utilité des liens vers des pages plus détaillées. Je pense que tu n'as juste pas saisie le but du topic : il ne s'agit pas d'un index d'articles détaillés sur chaque algo, mais d'un index regroupant des implémentations dans divers langages que les programmeurs pourront alors piocher. La brève description, c'est surtout pour ne pas balancer un code tout nu. Remarque par ailleurs que j'insiste beaucoup plus sur l'explication du code, vu que c'est là le véritable but du topic (les codes). Si les gens, comme tu l'as si bien dit, cherche un article détaillé, ils feront sans doute appel à Wikipédia, normal.
Si tu as un code plus clair à proposer (ce qui m'étonnerait) ou si tu souhaites continuer cette discussion plus en détail, préfère m'envoyer un MP.
Ouais, mais piocher un algo tout fait, c'est rarement une bonne idée, parce qu'après on arrive souvent mal à l'adapter à son code. Et pour le tri fusion, c'est suffisamment simple pour être trouvé tout seul...
Ouais, mais piocher un algo tout fait, c'est rarement une bonne idée, parce qu'après on arrive souvent mal à l'adapter à son code. Et pour le tri fusion, c'est suffisamment simple pour être trouvé tout seul...
Pas d'accord. Le fait que cela te paraisse simple, c'est parce que là, il s'agit d'un code OCaml. En réalité, si tu regardes des implémentations en C, c'est pas trivial du tout comme code (bon, en C++, on peut utiliser des fonctions toutes faites comme std::merge). Pour l'adaptation du code, je pense que le mieux est encore de ne pas trop le regarder (sauf si l'on est curieux) mais de juste se soucier de son prototype (c'est un peu la même chose pour les codes de la STL en C++). Après, il n'y a certes pas que les tris ou les algorithmes totalement indépendants.
L'algorithme d'Euclide permet de calculer le plus grand diviseur commun (PGCD) de deux entiers a et b. On l'utilise en général quand on ne connait pas la décomposition en produits de facteurs premiers de a et de b. L'article Wikipédia ici est assez complet et je vous conseille aussi de jeter un œil à l'algorithme étendu, ici.
[OCaml] Implémentation
Sans se prendre la tête, ci-dessous une implémentation très simple présentant l'algorithme de manière récursive (comme on le fait quasiment toujours) :
let rec pgcd a b = match b with
| 0 -> a
| _ -> pgcd b (a mod b)
Le tri par sélection est un algorithme de tri sélectionnant le plus petit élément dans la liste à trier, puis appliquant un nouveau tri par sélection (définition récursive) à la liste privée de ce minimum. Si la liste est un singleton (ou arrive à un singleton), on ne fait rien, l'unique élément est déjà "le plus petit". On renvoie finalement la liste des minima obtenus dans l'ordre. C'est la liste de départ triée. Pour aller plus loin, l'article Wikipédia ici.
Complexité
La complexité du tri par sélection est toujours en O(n²), on ne l'utilise quasiment jamais en pratique.
[C] Implémentation
Dans cette implémentation tail-rec en C (également valide en C++), c'est un tableau qui est utilisé et non une liste. Le principe ne change néanmoins pas : soit une partition begin jusqu'à end ; on trouve le plus petit élément de begin à end et on l'échange avec begin ; on appelle ensuite le tri par sélection sur la partition begin+1 jusqu'à end.
void tri_selection(int* array, int begin, int end)
{
int min = begin, i, temp;
if(begin >= end) return;
for(i = begin+1; i <= end; ++i)
if(array[i] < array[min]) min = i;
temp = array[begin];
array[begin] = array[min];
array[min] = temp;
tri_selection(array, begin+1, end);
}
Voici une autre implémentation, en OCaml, utilisant les listes. La fonction sélection renvoie le plus petit élément (trouvé avec find_min) et la liste privée de cet élément (construite avec del_min) sous forme d'une paire. La fonction tri_selection renvoie le minimum de la liste en cours suivie d'un tri par sélection sur la liste privée de cet élément.
let rec del_min m = function
| [] -> []
| t::q -> if t = m then q
else t::del_min m q
let rec find_min m = function
| [] -> m
| t::q -> if t < m then find_min t q
else find_min m q
let selection = function
| [] -> failwith "liste vide"
| t::q as l -> let m = find_min t q
in (m, del_min m l)
let rec tri_selection = function
| [] -> []
| l -> let m, r = selection l
in m::tri_selection r
La liste résultat est construite récursivement.
A chaque étape, on extrait le minimum de la liste fournie en argument et la liste résultat est construite en ajoutant en tête cet élément minimum au reste de la liste trie par sélection.
Le minimum de la liste est obtenu en retour de récursivité :
le minimum d'une liste composée d'un élément est cet élément.
La boucle récursive consiste à isoler le premier élément de la liste et à aller chercher le minimum de la liste restant.
On compare ensuite ce minimum à l'élément isolé.
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Merci à vous pour cette participation. J'édite de suite l'index.
joel76 : Il faudra quand même éviter de présenter plus d'un code par post, bon pour deux, ce n'est pas encore gênant.
Une implémentation du tri par sélection, très concise, en C++. L'idée reste la même que celle du code en C (voir index) sauf que l'on utilise les iterator et les algorithmes de la STL (bibliothèque standard du C++), ici std::iter_swap et std::min_element. On trie ici un vector d'entier, il est simple de changer ce type (il suffit de modifier le typedef) ou même de faire une fonction polymorphe.
Voici une implémentation assez concise du tri fusion en C++. On s'épargne l'écriture de la fonction de fusion en utilisant astucieusement std::inplace_merge de la STL. Dans ce code, je n'utilise pas les iterator car pour trouver une adresse moyenne ((b+e)/2), c'est quand même pas trivial. Le code reste correct et bien clair. À noter que l (pour "last") est inclus dans les indices des valeurs à trier.
Robocop : Pour aller plus loin, on peut généraliser ton algorithme pour s'approcher d'un zéros de n'importe quelle fonction (sous reserve de commencer pas trop loin). Il ne s'agit ni plus ni moins que de la méthode de Newton. De là on peut trouver facilement le moyen d'extraire une racine n-ème par exemple.
% le tri fusion
%
% Si la liste au un seul élément
% elle est triée
tri_fusion([X], [X]) :- !.
% sinon
tri_fusion(LIn, LOut) :-
% on split la liste
split(LIn, L1, L2),
% on trie le deux sous listes
tri_fusion(L1, L11),
tri_fusion(L2, L22),
% on les fusionne
fusion(L11, L22, LOut).
% la fusion
%
% si la deuxième liste est vide
% la fusion donne la premiere liste
fusion(X, [], X) :- !.
% si la première liste est vide
% la fusion donne la deuxième liste
fusion([], X, X) :- !.
% on compare les premiers éléments de chaque liste
% H1 est plus petit que H2, donc on fusionne le reste de la
% première liste T1 avec la deuxième liste
% et on ajoute en tête du résultat H1.
fusion([H1 | T1], [H2 | T2], [H1 | L]) :-
H1 < H2, !,
fusion(T1, [H2 | T2], L).
% ici on est sûr (à cause du cut '!') que
% H1 est plus grand que H2
fusion([H1 | T1], [H2 | T2], [H2 | L]) :-
fusion([H1 |T1], T2, L).
% le split
%
% Les cas particuliers du split :
%
% Un seul élément, mis dans la première liste
split([X], [X], []) :- !.
% Deux éléments, répartis dans les deux listes
split([X, Y], [X], [Y]).
% cas général, on isole les deux premiers éléments dee la liste
% on split le reste
% on distribue les deux éléments dans les deux listes.
split([H1, H2 | T], [H1 | X1], [H2 | X2]) :-
split(T, X1, X2).
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Le principe, récursif, est simple : on divise la structure à trier en deux parties a et b à partir d'une valeur pivot tel que toutes les valeurs de a soient inférieures ou égales aux valeurs de b. On trie ensuite a et b indépendamment avec le tri rapide. Ici ou ici pour en savoir plus.
Complexité
La complexité au meilleur des cas est en O(n log n) mais au pire des cas, nous avons du O(n²). Le complexité moyenne est en O(n log n).
[OCaml] Implémentation
La fonction partition coupe la liste à trier en deux comme décrit ci-dessus. Pour la fonction tri_rapide, il faut distinguer trois cas : soit la liste est vide ou est un singleton, auquel cas, c'est trié et on renvoie cette liste ; soit nous avons une tête suivie d'une queue. Dans ce cas, on partitionne la queue en a et b en prenant la tête pour pivot. On trie a, on trie b et on renvoie la liste résultant de la concaténation a, pivot, b. Au final, la liste d'entrée est triée.
let rec partition p a b = function
| [] -> (a, b)
| t::q ->
if t < p then partition p (t::a) b q
else partition p a (t::b) q
let rec tri_rapide = function
| ([] | [_]) as l -> l
| t::q -> let a, b = partition t [] [] q
in (tri_rapide a) @ [t] @ (tri_rapide b)
Premièrement, la définition n'est pas rigoureuse (égalité ?) mais de plus, tu ne te sens pas concerné par la présentation mise en place pour une homogénéité.
Pour parler franchement, ça m'emmerde. Si vous voulez pas de mes codes, ok. Pas envie de me casser la tête à faire une présentation arbitraire alors qu'une explication suffit.
Voici une autre implémentation du tri rapide en C++ utilisant la fonction de partitionnement de la STL std::partition. On prend la dernière valeur de la série en cours pour pivot, on partitionne selon ce pivot (utilisation de std::bind2nd pour le prédicat) avant de placer ce pivot à la bonne place (le std::iter_swap dans ce code). Il suffit donc ensuite d'appliquer une tri rapide à la première partition, puis à la deuxième partition, le pivot exclu des deux : on n'y touche plus. Comme d'habitude, l'iterator end n'appartient pas aux valeurs à trier.
typedef std::vector<int>::iterator it;
void tri_rapide(it begin, it end)
{
if(begin >= end) return; end--;
it m = std::partition(begin, end, std::bind2nd(std::less<int>(),*end));
std::iter_swap(m, end);
tri_rapide(begin, m);
tri_rapide(m+1, end+1);
}
Algorithmes divers sur séquences : Mélanger aléatoirement une séquence
Principe
La technique la plus courante pour mélanger une structure aléatoirement (tableau, liste, ...), est d'itérer sur la structure et d'échanger chaque élément avec un autre sélectionné aléatoirement (en pratique pseudo-aléatoirement). Cette technique donne de très bons résultats et est celle utilisée dans l'implémentation de la STL de gnu (std::random_shuffle).
Complexité
La complexité de cet algorithme est en O(n) sur les tableaux. Sur les listes chaînées, l'algorithme en place est en O(n²) mais on peut passer temporairement par un tableau et obtenir du O(n) au prix d'une complexité mémoire en O(n).
[OCaml] Implémentation
Dans l'implémentation OCaml présentée plus bas, on utilise les tableaux. On définit une fonction swap permettant de permuter deux éléments dans t, le tableau. On parcourt ensuite ce tableau, passé en paramètre, et on permute chaque élément avec un autre, dont l'indice est trouvé à partir de f. f doit être une fonction générant un nombre pseudo-aléatoire entre 0 et la valeur de son unique paramètre (exclue) ; Random.int convient parfaitement.
let shuffle t f =
let swap i j =
let tmp = t.(i) in
t.(i) <- t.(j) ;
t.(j) <- tmp in
for i = Array.length t - 1 downto 1 do
swap i (f (i + 1))
done
Voici un test effectué :
# let a = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|];;
val a : int array = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|]
# shuffle a Random.int;;
- : unit = ()
# a;;
- : int array = [|8; 1; 9; 6; 7; 2; 0; 4; 3; 5|]
Plus bas, une autre implémentation, en C++. La fonction array_shuffle prend en paramètre b, un iterator sur la première valeur de la séquence, e, un iterator marquant la fin de la séquence (e est exclu) et rand_f qui est une fonction générant un nombre pseudo-aléatoire (l'utilisateur peut utiliser le rand() standard où utiliser autre chose). Ensuite, rien de nouveau : en parcourant la séquence, on échange chaque élément avec un autre, sélectionné pseudo-aléatoirement.
template <typename Rand, typename It>
void array_shuffle(It b, It e, Rand rand_f)
{
while(b!=e) std::iter_swap(b++, b+(rand_f()%(e-b)));
}
Cette implémentation est là uniquement à titre informatif puisqu'en C++ pratique, on utilisera naturellement std::random_shuffle.
Argument convaincant numéro 1 : peux-tu prouver que l'implémentation répartit uniformément les éléments ?
Argument convaincant numéro 2 :
let mesure shuffle taille nb_iter =
let table = Hashtbl.create nb_iter in
for i = 1 to nb_iter do
let test = Array.init taille (fun k -> k) in
shuffle test;
try Hashtbl.replace table test (Hashtbl.find table test + 1)
with Not_found -> Hashtbl.add table test 0
done;
List.sort (fun a b -> compare (snd a) (snd b))
(Hashtbl.fold
(fun tab elem li -> (tab, elem) :: li) table [])
# mesure (fun tab -> array_shuffle tab Random.int) 3 100000;;
- : (int array * int) list =
[([|1; 2; 0|], 18784); ([|0; 2; 1|], 18476); ([|1; 0; 2|], 18425);
([|2; 1; 0|], 14938); ([|2; 0; 1|], 14783); ([|0; 1; 2|], 14588)]
Voici une implémentation correcte :
let swap t i j =
let tmp = t.(i) in
t.(i) <- t.(j) ;
t.(j) <- tmp
let shuffle tab =
for i = Array.length tab - 1 downto 1 do
swap tab i (Random.int (i + 1))
done
Argument 1 (idée de la preuve) : tous les éléments ont autant de chance d'atterir en dernière position, et sachant cela on voit bien que tous les éléments restants (pas choisis pour aller en dernière position) on autant de chance d'atterir en avant-dernière, etc.
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !