lemon/radix_sort.h
changeset 680 257e91516e09
parent 444 ba49101c9b07
child 1042 d450a02728d0
equal deleted inserted replaced
3:1a43d1e5f7f0 4:a1eda04674f1
   203   /// It is also possible to use a normal function instead
   203   /// It is also possible to use a normal function instead
   204   /// of the functor object. If the functor is not given it will use
   204   /// of the functor object. If the functor is not given it will use
   205   /// the identity function instead.
   205   /// the identity function instead.
   206   ///
   206   ///
   207   /// This is a special quick sort algorithm where the pivot
   207   /// This is a special quick sort algorithm where the pivot
   208   /// values to split the items are choosen to be \f$ 2^k \f$ for each \c k.
   208   /// values to split the items are choosen to be 2<sup>k</sup>
   209   /// Therefore, the time complexity of the
   209   /// for each \c k.
   210   /// algorithm is \f$ O(\log(c)n) \f$ and it uses \f$ O(\log(c)) \f$,
   210   /// Therefore, the time complexity of the algorithm is O(log(c)*n) and
   211   /// additional space, where \c c is the maximal value and \c n is the
   211   /// it uses O(log(c)) additional space, where \c c is the maximal value
   212   /// number of the items in the container.
   212   /// and \c n is the number of the items in the container.
   213   ///
   213   ///
   214   /// \param first The begin of the given range.
   214   /// \param first The begin of the given range.
   215   /// \param last The end of the given range.
   215   /// \param last The end of the given range.
   216   /// \param functor An adaptible unary function or a normal function
   216   /// \param functor An adaptible unary function or a normal function
   217   /// which maps the items to any integer type which can be either
   217   /// which maps the items to any integer type which can be either
   428   ///
   428   ///
   429   /// This sort algorithm  use a radix forward sort on the
   429   /// This sort algorithm  use a radix forward sort on the
   430   /// bytes of the integer number. The algorithm sorts the items
   430   /// bytes of the integer number. The algorithm sorts the items
   431   /// byte-by-byte. First, it counts how many times a byte value occurs
   431   /// byte-by-byte. First, it counts how many times a byte value occurs
   432   /// in the container, then it copies the corresponding items to
   432   /// in the container, then it copies the corresponding items to
   433   /// another container in asceding order in \c O(n) time.
   433   /// another container in asceding order in O(n) time.
   434   ///
   434   ///
   435   /// The time complexity of the algorithm is \f$ O(\log(c)n) \f$ and
   435   /// The time complexity of the algorithm is O(log(c)*n) and
   436   /// it uses \f$ O(n) \f$, additional space, where \c c is the
   436   /// it uses O(n) additional space, where \c c is the
   437   /// maximal value and \c n is the number of the items in the
   437   /// maximal value and \c n is the number of the items in the
   438   /// container.
   438   /// container.
   439   ///
   439   ///
   440 
   440 
   441   /// \param first The begin of the given range.
   441   /// \param first The begin of the given range.