Changeset - r465:31d224a3c0af
« 464:4f7224
466: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 6 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
6 6 
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
... ... 
@@ -195,26 +195,29 @@
195 195 
  ///
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.
214 215 
  /// \param last The end of the given range.
215 216 
  /// \param functor An adaptible unary function or a normal function
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) {
220 223 
    using namespace _radix_sort_bits;
... ... 
@@ -413,34 +416,33 @@
413 416 

			




	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.


			




	441
	442
	
		
  /// \param functor An adaptible unary function or a normal function


			




	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) {


			




	446
	448
	
		
    using namespace _radix_sort_bits;

			




        

    

    

    

        

            

                

                    test/radix_sort_test.cc
                

                

                  
                  
                  
                  Show white space
                  6 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


			




	6
	6
	
		
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport


			




        

    






    
    



    


    

     
    
0 comments (0 inline)