aapl/bubblesort.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_BUBBLESORT_H
  23 #define _AAPL_BUBBLESORT_H
  24
  25 #ifdef AAPL_NAMESPACE
  26 namespace Aapl {
  27 #endif
  28
  29 /**
  30  * \addtogroup sort
  31  * @{
  32  */
  33
  34 /**
  35  * \class BubbleSort
  36  * \brief Bubble sort an array of data.
  37  *
  38  * BubbleSort can be used to sort any array of objects of type T provided a
  39  * compare class is given. BubbleSort 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  * BubbleSort runs in O(n^2) time. It is most useful when sorting arrays that
  47  * are nearly sorted. It is best when neighbouring pairs are out of place.
  48  * BubbleSort is a stable sort, meaning that objects with the same key have
  49  * their relative ordering preserved.
  50  */
  51
  52 /*@}*/
  53
  54 /* BubbleSort. */
  55 template <class T, class Compare> class BubbleSort
  56         : public Compare
  57 {
  58 public:
  59         /* Sorting interface routine. */
  60         void sort(T *data, long len);
  61 };
  62
  63
  64 /**
  65  * \brief Bubble sort an array of data.
  66  */
  67 template <class T, class Compare> void BubbleSort<T,Compare>::
  68                 sort(T *data, long len)
  69 {
  70         bool changed = true;
  71         for ( long pass = 1; changed && pass < len; pass ++ ) {
  72                 changed = false;
  73                 for ( long i = 0; i < len-pass; i++ ) {
  74                         /* Do we swap pos with the next one? */
  75                         if ( compare( data[i], data[i+1] ) > 0 ) {
  76                                 char tmp[sizeof(T)];
  77
  78                                 /* Swap the two items. */
  79                                 memcpy( tmp, data+i, sizeof(T) );
  80                                 memcpy( data+i, data+i+1, sizeof(T) );
  81                                 memcpy( data+i+1, tmp, sizeof(T) );
  82
  83                                 /* Note that we made a change. */
  84                                 changed = true;
  85                         }
  86                 }
  87         }
  88 }
  89
  90 #ifdef AAPL_NAMESPACE
  91 }
  92 #endif
  93
  94 #endif /* _AAPL_BUBBLESORT_H */