aapl/insertsort.h

   1 /*
   2  *  Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca>
   3  */
   4
   5 /*  This file is part of Aapl.
   6  *
   7  *  Aapl is free software; you can redistribute it and/or modify it under the
   8  *  terms of the GNU Lesser General Public License as published by the Free
   9  *  Software Foundation; either version 2.1 of the License, or (at your option)
  10  *  any later version.
  11  *
  12  *  Aapl is distributed in the hope that it will be useful, but WITHOUT ANY
  13  *  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  14  *  FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
  15  *  more details.
  16  *
  17  *  You should have received a copy of the GNU Lesser General Public License
  18  *  along with Aapl; if not, write to the Free Software Foundation, Inc., 59
  19  *  Temple Place, Suite 330, Boston, MA 02111-1307 USA
  20  */
  21
  22 #ifndef _AAPL_INSERTSORT_H
  23 #define _AAPL_INSERTSORT_H
  24
  25 #ifdef AAPL_NAMESPACE
  26 namespace Aapl {
  27 #endif
  28
  29 /**
  30  * \addtogroup sort
  31  * @{
  32  */
  33
  34 /**
  35  * \class InsertSort
  36  * \brief Insertion sort an array of data.
  37  *
  38  * InsertSort can be used to sort any array of objects of type T provided a
  39  * compare class is given. InsertSort is in-place. It does not require any
  40  * temporary storage.
  41  *
  42  * Objects are not made aware that they are being moved around in memory.
  43  * Assignment operators, constructors and destructors are never invoked by the
  44  * sort.
  45  *
  46  * InsertSort runs in O(n^2) time. It is most useful when sorting small arrays.
  47  * where it can outperform the O(n*log(n)) sorters due to its simplicity.
  48  * InsertSort is a not a stable sort. Elements with the same key will not have
  49  * their relative ordering preserved.
  50  */
  51
  52 /*@}*/
  53
  54 /* InsertSort. */
  55 template <class T, class Compare> class InsertSort
  56         : public Compare
  57 {
  58 public:
  59         /* Sorting interface routine. */
  60         void sort(T *data, long len);
  61 };
  62
  63
  64 /**
  65  * \brief Insertion sort an array of data.
  66  */
  67 template <class T, class Compare>
  68         void InsertSort<T,Compare>::sort(T *data, long len)
  69 {
  70         /* For each next largest spot in the sorted array... */
  71         for ( T *dest = data; dest < data+len-1; dest++ ) {
  72                 /* Find the next smallest element in the unsorted array. */
  73                 T *smallest = dest;
  74                 for ( T *src = dest+1; src < data+len; src++ ) {
  75                         /* If src is smaller than the current src, then use it. */
  76                         if ( compare( *src, *smallest ) < 0 )
  77                                 smallest = src;
  78                 }
  79
  80                 if ( smallest != dest ) {
  81                         /* Swap dest, smallest. */
  82                         char tmp[sizeof(T)];
  83                         memcpy( tmp, dest, sizeof(T) );
  84                         memcpy( dest, smallest, sizeof(T) );
  85                         memcpy( smallest, tmp, sizeof(T) );
  86                 }
  87         }
  88 }
  89
  90 #ifdef AAPL_NAMESPACE
  91 }
  92 #endif
  93
  94 #endif /* _AAPL_INSERTSORT_H */