Partage
  • Partager sur Facebook
  • Partager sur Twitter

Algorithmes divers multi-langage

tris, pathfinder, calcul, matrice, etc.

    11 mai 2009 à 22:02:38

    Index : liste des algorithmes


    Algorithmes de tri



    Algorithmes divers sur séquence



    Algorithmes sur arbre binaire de recherche (ABR)



    Combinatoire



    Calculs divers



    Chaine de caractères



    Fonctions mathématiques



    Pathfinder



    Structures de données




    Bonjour à tous !

    But du topic


    Image utilisateur
    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>

    Image utilisateur
    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.

    Merci à vous tous et à bientôt !
    shareman
    • Partager sur Facebook
    • Partager sur Twitter
      12 mai 2009 à 19:44:40

      Tri : Tri fusion



      Principe


      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)
      
      • Partager sur Facebook
      • Partager sur Twitter
        12 mai 2009 à 20:05:40

        Euh, je veux pas venir foutre le bazar, mais ton code est bizarre.
        _ as l -> : 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.
        • Partager sur Facebook
        • Partager sur Twitter
          12 mai 2009 à 20:30:00

          Citation : Maxibolt

          _ as l -> : d'où tu sors ça ?


          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.
          • Partager sur Facebook
          • Partager sur Twitter
            12 mai 2009 à 20:50:06

            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...
            • Partager sur Facebook
            • Partager sur Twitter
              12 mai 2009 à 21:29:48

              Citation : Maxibolt

              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.
              • Partager sur Facebook
              • Partager sur Twitter
                12 mai 2009 à 21:48:23

                Calculs divers : Algorithme d'Euclide



                Principe


                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)
                
                • Partager sur Facebook
                • Partager sur Twitter
                  12 mai 2009 à 23:02:03

                  Moi j'aime bien, ça permet de présenter un peu les différents langages. Au moins leur syntaxe.
                  • Partager sur Facebook
                  • Partager sur Twitter
                    13 mai 2009 à 16:46:58

                    Citation : Aerius

                    Moi j'aime bien, ça permet de présenter un peu les différents langages. Au moins leur syntaxe.


                    Euh pourquoi pas mais c'est pas le but cherché.
                    • Partager sur Facebook
                    • Partager sur Twitter
                      13 mai 2009 à 17:11:38

                      Tri : Tri par sélection


                      Principe


                      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);
                      }
                      
                      • Partager sur Facebook
                      • Partager sur Twitter
                        13 mai 2009 à 17:32:58

                        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
                        
                        • Partager sur Facebook
                        • Partager sur Twitter
                          13 mai 2009 à 19:55:43

                          Fonction mathématique : calcul d'une racine carrée


                          Principe


                          La méthode se base sur l'approximation affine, qui permet d'obtenir la suite suivante : <math>\(U_{n+1} = \frac{1}{2*Un}*(x-Un^2) + Un\)</math>.
                          Plus d'info ici : http://mathema.alwaysdata.net/index.ph [...] acine-carrée

                          [Ocaml] Implémentation


                          let racine_carre n = 
                             let rec rc x un = function
                                 0 -> un
                               | n -> rc x ((1./.(2.*.un)) *. (x -. un**2.) +. un) (n-1)
                             in rc n 2. 5
                          
                          • Partager sur Facebook
                          • Partager sur Twitter
                            13 mai 2009 à 20:59:48

                            Voici une implémentation du tri sélection en Prolog :
                            tri_selection([], []).
                            
                            tri_selection(L, [H | L1]) :-
                            	minimum(L, H, L0),
                            	tri_selection(L0, L1).
                            
                            
                            minimum([H], H, []).
                            
                            minimum([H | T], H1, T1) :-
                            	minimum(T, H0, T0),
                            	(   H < H0 -> 
                            	    H1 = H, T1 = T;
                            	    H1 = H0, T1 = [H | T0]).
                            

                            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é.
                            • Partager sur Facebook
                            • Partager sur Twitter

                            Le crayon la gomme et le papier sont les meilleurs outils du programmeur !

                              13 mai 2009 à 21:15:56

                              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.
                              • Partager sur Facebook
                              • Partager sur Twitter
                                13 mai 2009 à 21:18:24

                                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.

                                typedef std::vector<int>::iterator it;
                                
                                void tri_selection(it begin, it end)
                                {
                                    if(begin >= end-1) return;
                                    std::iter_swap(begin, std::min_element(begin, end));
                                    tri_selection(begin+1, end);
                                }
                                
                                • Partager sur Facebook
                                • Partager sur Twitter
                                  13 mai 2009 à 21:41:36

                                  Ok pour la remarque :

                                  Implémentation du calcul du PGCD en Prolog :
                                  pgcd0(X, 0, X) :- !.
                                  
                                  pgcd0(A, B, C) :-
                                  	A1 is A mod B,
                                  	pgcd0(B, A1, C).
                                  
                                  pgcd(A, B, X) :-
                                  	A < B -> pgcd0(B, A, X); pgcd0(A, B, X).
                                  
                                  (Ce code tient compte de la possibilité qu'au départ a soit plus petit que b)

                                  • Partager sur Facebook
                                  • Partager sur Twitter

                                  Le crayon la gomme et le papier sont les meilleurs outils du programmeur !

                                    13 mai 2009 à 21:58:49

                                    Merci. ;)

                                    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.

                                    void tri_fusion(std::vector<int>& v, int f, int l)
                                    {
                                        if(f >= l) return;
                                        tri_fusion(v, f, (f+l)/2);
                                        tri_fusion(v, (f+l)/2+1, l);
                                        std::inplace_merge(v.begin()+f, v.begin()+(f+l)/2+1, v.begin()+l+1);
                                    }
                                    
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      13 mai 2009 à 22:03:12

                                      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.
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        13 mai 2009 à 22:10:38

                                        Le tri fusion en Prolog :

                                        % 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).
                                        • Partager sur Facebook
                                        • Partager sur Twitter

                                        Le crayon la gomme et le papier sont les meilleurs outils du programmeur !

                                          13 mai 2009 à 23:31:10

                                          Bon finalement plus rien.
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            14 mai 2009 à 0:23:10

                                            Algorithmes de tri : Tri rapide


                                            Principe


                                            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)
                                            

                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              14 mai 2009 à 0:33:15

                                              "on concatène les éléments de la liste inférieurs au pivot (ici, le prermier élément), le pivot et les éléments qui lui sont supérieurs."

                                              C'était pas une brève explication ça ? Si tu veux, je retire mon post...
                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                14 mai 2009 à 0:45:32

                                                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é.
                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                  14 mai 2009 à 8:18:17

                                                  Oui, respectez la présentation, ça ne coute pas grand chose, et ça donne de la cohérence au topic.
                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                    14 mai 2009 à 12:00:26

                                                    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.
                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                      14 mai 2009 à 22:28:13

                                                      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);
                                                      }
                                                      
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        15 mai 2009 à 23:00:34

                                                        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|]
                                                        
                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                          15 mai 2009 à 23:27:10

                                                          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.
                                                          • Partager sur Facebook
                                                          • Partager sur Twitter
                                                            16 mai 2009 à 11:58:41

                                                            L'implémentation du shuffle n'est pas bonne.

                                                            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.
                                                            • Partager sur Facebook
                                                            • Partager sur Twitter
                                                              16 mai 2009 à 17:43:36

                                                              Très juste, je vais éditer. Merci.
                                                              • Partager sur Facebook
                                                              • Partager sur Twitter

                                                              Algorithmes divers multi-langage

                                                              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                                              × Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
                                                              • Editeur
                                                              • Markdown