Changeset - r442:31d224a3c0af
« 441:4f7224
443:de16f1 »
gravatar
alpar (Alpar Juttner)
alpar@cs.elte.hu
Doc improvements and source unification in radix_sort (#72)
0 2 0
default
2 files changed with 37 insertions and 35 deletions:
lemon/radix_sort.h
35
33
test/radix_sort_test.cc
2
2
↑ Collapse diff ↑
lemon/radix_sort.h
Show white space 4 line context
1 
/* -*- C++ -*-
1 
/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 2 
 *
3 
 * This file is a part of LEMON, a generic C++ optimization library
3 
 * This file is a part of LEMON, a generic C++ optimization library.
4 4 
 *
5 5 
 * Copyright (C) 2003-2008
... ... 
@@ -196,18 +196,19 @@
196 196 
  /// \brief Sorts the STL compatible range into ascending order.
197 197 
  ///
198 
  /// The \c radixSort sorts the STL compatible range into ascending
199 
  /// order.  The radix sort algorithm can sort the items which mapped
200 
  /// to an integer with an adaptable unary function \c functor and the
201 
  /// order will be ascending by these mapped values. As function
202 
  /// specialization it is possible to use a normal function instead
203 
  /// of the functor object or if the functor is not given it will use
204 
  /// an identity function instead.
198 
  /// The \c radixSort sorts an STL compatible range into ascending
199 
  /// order.  The radix sort algorithm can sort items which are mapped
200 
  /// to integers with an adaptable unary function \c functor and the
201 
  /// order will be ascending according to these mapped values.
205 202 
  ///
206 
  /// This implemented radix sort is a special quick sort which pivot
207 
  /// value is choosen to partite the items on the next
208 
  /// bit. Therefore, let be \c c the maximal capacity and \c n the
209 
  /// number of the items in the container, the time complexity of the
210 
  /// algorithm is \f$ O(\log(c)n) \f$ and the additional space
211 
  /// complexity is \f$ O(\log(c)) \f$.
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
205 
  /// the identity function instead.
206 
  ///
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.
209 
  /// Therefore, the time complexity of the
210 
  /// algorithm is \f$ O(\log(c)n) \f$ and it uses \f$ O(\log(c)) \f$,
211 
  /// additional space, where \c c is the maximal value and \c n is the
212 
  /// number of the items in the container.
212 213 
  ///
213 214 
  /// \param first The begin of the given range.
... ... 
@@ -216,4 +217,6 @@
216 217 
  /// which maps the items to any integer type which can be either
217 218 
  /// signed or unsigned.
219 
  ///
220 
  /// \sa counterSort()
218 221 
  template <typename Iterator, typename Functor>
219 222 
  void radixSort(Iterator first, Iterator last, Functor functor) {
... ... 
@@ -414,27 +417,25 @@
414 417 
  /// \ingroup auxalg
415 418 
  ///
416 
  /// \brief Sorts stable the STL compatible range into ascending order.
419 
  /// \brief Sorts the STL compatible range into ascending order in a stable
420 
  /// way.
417 421 
  ///
418 
  /// The \c counterSort sorts the STL compatible range into ascending
419 
  /// order.  The counter sort algorithm can sort the items which
420 
  /// mapped to an integer with an adaptable unary function \c functor
421 
  /// and the order will be ascending by these mapped values. As
422 
  /// function specialization it is possible to use a normal function
423 
  /// instead of the functor object or if the functor is not given it
424 
  /// will use an identity function instead.
422 
  /// This function sorts an STL compatible range into ascending
423 
  /// order according to an integer mapping in the same as radixSort() does.
425 424 
  ///
426 
  /// The implemented counter sort use a radix forward sort on the
425 
  /// This sorting algorithm is stable, i.e. the order of two equal
426 
  /// element remains the same after the sorting.
427 
  ///
428 
  /// This sort algorithm  use a radix forward sort on the
427 429 
  /// bytes of the integer number. The algorithm sorts the items
428 
  /// byte-by-byte, first it counts how many times occurs a byte value
429 
  /// in the containerm, and with the occurence number the container
430 
  /// can be copied to an other in asceding order in \c O(n) time.
431 
  /// Let be \c c the maximal capacity of the integer type and \c n
432 
  /// the number of the items in the container, the time complexity of
433 
  /// the algorithm is \f$ O(\log(c)n) \f$ and the additional space
434 
  /// complexity is \f$ O(n) \f$.
430 
  /// byte-by-byte. First, it counts how many times a byte value occurs
431 
  /// in the container, then it copies the corresponding items to
432 
  /// another container in asceding order in \c O(n) time.
435 433 
  ///
436 
  /// The sorting algorithm is stable, i.e. the order of two equal
437 
  /// element remains the same.
434 
  /// The time complexity of the algorithm is \f$ O(\log(c)n) \f$ and
435 
  /// it uses \f$ O(n) \f$, additional space, where \c c is the
436 
  /// maximal value and \c n is the number of the items in the
437 
  /// container.
438 438 
  ///
439 

			




	439
	440
	
		
  /// \param first The begin of the given range.


			




	440
	441
	
		
  /// \param last The end of the given range.


			




	...
	...
	
		
@@ -442,4 +443,5 @@


			




	442
	443
	
		
  /// which maps the items to any integer type which can be either


			




	443
	444
	
		
  /// signed or unsigned.


			




	
	445
	
		
  /// \sa radixSort()


			




	444
	446
	
		
  template <typename Iterator, typename Functor>


			




	445
	447
	
		
  void counterSort(Iterator first, Iterator last, Functor functor) {

			




        

    

    

    

        

            

                

                    test/radix_sort_test.cc
                

                

                  
                  
                  
                  Show white space
                  4 line context
                

                
                  
                
            

        

        

            

            



	1
	
	
		
/* -*- C++ -*-


			




	
	1
	
		
/* -*- mode: C++; indent-tabs-mode: nil; -*-


			




	2
	2
	
		
 *


			




	3
	
	
		
 * This file is a part of LEMON, a generic C++ optimization library


			




	
	3
	
		
 * This file is a part of LEMON, a generic C++ optimization library.


			




	4
	4
	
		
 *


			




	5
	5
	
		
 * Copyright (C) 2003-2008


			




        

    






    
    



    


    

     
    
0 comments (0 inline)