bogo_sort.hpp

Go to the documentation of this file.

#ifndef LIBJMMCG_CORE_BOGO_SORT_HPP
#define LIBJMMCG_CORE_BOGO_SORT_HPP
 
/******************************************************************************
** Copyright © 2004 by J.M.McGuiness, coder@hussar.me.uk
**
** This library is free software; you can redistribute it and/or
** modify it under the terms of the GNU Lesser General Public
** License as published by the Free Software Foundation; either
** version 2.1 of the License, or (at your option) any later version.
**
** This library is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
** Lesser General Public License for more details.
**
** You should have received a copy of the GNU Lesser General Public
** License along with this library; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
 
#include "config.h"
 
#include <algorithm>
 
namespace jmmcg { namespace LIBJMMCG_VER_NAMESPACE {
 
   /// An implementation of the bogo-sort[1] algorithm, in STL-style.
   /**
      Apologies to all members of the C++ standards community for this perversion.
      This algorithm should never be used in any code, apart from as an example of easy it is to create an apparently innocuous algorithm which can have an exceptionally bad order.
 
      I quote an edited excerpt of a discussion on the ACCU-General mailing list regarding this implementation:
      "The quest for perversity was clearly at odds with the quest for beauty.  I think perversity wins out in this case.
 
      And yes, you're a very bad man. How about compounding your badness and just writing this little gem up for Overload or blogging it so that it becomes immortalised and searchable? >:->
 
      Kevlin [Henney]"
 
      \param first The start of the input range.
      \param last The end of the input range.
      \param comp The comparator to be used to compare two values within the range.
 
      Complexity: the *truly* excessive and exorbitant: O(N*N!+N*N)=O(N*N!), c.f. with O(nlog(n)) of std::sort().
 
      [1] <a href="http://www.tcs.ifi.lmu.de/~gruberh/data/fun07-final.pdf"/>
 
      \see std::sort()
   */
   template<class Iter, class Compare> inline void FORCE_INLINE
   bogo_sort(Iter first, Iter last, Compare comp) {
      /*
         Note that this technique (the suggester shall remain nameless to protect the innocent) is used:
 
         "The elegant beauty of
            while(std::next_permutation(first, last));
         is lost in your version.;-)"
      */
      while(std::next_permutation(first, last, comp));
   }
 
} }
 
#endif