aapl/quicksort.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_QUICKSORT_H
  23 #define _AAPL_QUICKSORT_H
  24
  25 #include "insertsort.h"
  26
  27 #ifdef AAPL_NAMESPACE
  28 namespace Aapl {
  29 #endif
  30
  31 /**
  32  * \addtogroup sort
  33  * @{
  34  */
  35
  36 /**
  37  * \class QuickSort
  38  * \brief Quick sort an array of data.
  39  *
  40  * QuickSort can be used to sort any array of objects of type T provided a
  41  * compare class is given. QuickSort is in-place. It does not require any
  42  * temporary storage.
  43  *
  44  * Objects are not made aware that they are being moved around in memory.
  45  * Assignment operators, constructors and destructors are never invoked by the
  46  * sort.
  47  *
  48  * QuickSort runs in O(n*log(n)) time in the average case. It is faster than
  49  * mergsort in the average case because it does less moving of data. The
  50  * performance of quicksort depends mostly on the choice of pivot. This
  51  * implementation picks the pivot as the median of first, middle, last. This
  52  * choice of pivot avoids the O(n^2) worst case for input already sorted, but
  53  * it is still possible to encounter the O(n^2) worst case. For example an
  54  * array of identical elements will run in O(n^2)
  55  *
  56  * QuickSort is not a stable sort. Elements with the same key will not have
  57  * their relative ordering preserved.  QuickSort switches to an InsertSort
  58  * when the size of the array being sorted is small. This happens when
  59  * directly sorting a small array or when QuickSort calls iteself recursively
  60  * on a small portion of a larger array.
  61  */
  62
  63 /*@}*/
  64
  65 /* QuickSort. */
  66 template <class T, class Compare> class QuickSort :
  67                 public InsertSort<T, Compare>
  68 {
  69 public:
  70         /* Sorting interface routine. */
  71         void sort(T *data, long len);
  72
  73 private:
  74         /* Recursive worker. */
  75         void doSort(T *start, T *end);
  76         T *partition(T *start, T *end);
  77         inline T *median(T *start, T *end);
  78 };
  79
  80 #define _QS_INSERTION_THRESH 16
  81
  82 /* Finds the median of start, middle, end. */
  83 template <class T, class Compare> T *QuickSort<T,Compare>::
  84                 median(T *start, T *end)
  85 {
  86         T *pivot, *mid = start + (end-start)/2;
  87
  88         /* CChoose the pivot. */
  89         if ( compare(*start, *mid) < 0  ) {
  90                 if ( compare(*mid, *end) < 0 )
  91                         pivot = mid;
  92                 else if ( compare(*start, *end) < 0 )
  93                         pivot = end;
  94                 else
  95                         pivot = start;
  96         }
  97         else if ( compare(*start, *end) < 0 )
  98                 pivot = start;
  99         else if ( compare(*mid, *end) < 0 )
 100                 pivot = end;
 101         else
 102                 pivot = mid;
 103
 104         return pivot;
 105 }
 106
 107 template <class T, class Compare> T *QuickSort<T,Compare>::
 108                 partition(T *start, T *end)
 109 {
 110         /* Use the median of start, middle, end as the pivot. First save
 111          * it off then move the last element to the free spot. */
 112         char pcPivot[sizeof(T)];
 113         T *pivot = median(start, end);
 114
 115         memcpy( pcPivot, pivot, sizeof(T) );
 116         if ( pivot != end )
 117                 memcpy( pivot, end, sizeof(T) );
 118
 119         T *first = start-1;
 120         T *last = end;
 121         pivot = (T*) pcPivot;
 122
 123         /* Shuffle element to the correct side of the pivot, ending
 124          * up with the free spot where the pivot will go. */
 125         while ( true ) {
 126                 /* Throw one element ahead to the free spot at last. */
 127                 while ( true ) {
 128                         first += 1;
 129                         if ( first == last )
 130                                 goto done;
 131                         if ( compare( *first, *pivot ) > 0 ) {
 132                                 memcpy(last, first, sizeof(T));
 133                                 break;
 134                         }
 135                 }
 136
 137                 /* Throw one element back to the free spot at first. */
 138                 while ( true ) {
 139                         last -= 1;
 140                         if ( last == first )
 141                                 goto done;
 142                         if ( compare( *last, *pivot ) < 0 ) {
 143                                 memcpy(first, last, sizeof(T));
 144                                 break;
 145                         }
 146                 }
 147         }
 148 done:
 149         /* Put the pivot into the middle spot for it. */
 150         memcpy( first, pivot, sizeof(T) );
 151         return first;
 152 }
 153
 154
 155 template< class T, class Compare> void QuickSort<T,Compare>::
 156                 doSort(T *start, T *end)
 157 {
 158         long len = end - start + 1;
 159         if ( len > _QS_INSERTION_THRESH ) {
 160                 /* Use quicksort. */
 161                 T *pivot = partition( start, end );
 162                 doSort(start, pivot-1);
 163                 doSort(pivot+1, end);
 164         }
 165         else if ( len > 1 ) {
 166                 /* Array is small, use insertion sort. */
 167                 InsertSort<T, Compare>::sort( start, len );
 168         }
 169 }
 170
 171 /**
 172  * \brief Quick sort an array of data.
 173  */
 174 template< class T, class Compare>
 175         void QuickSort<T,Compare>::sort(T *data, long len)
 176 {
 177         /* Call recursive worker. */
 178         doSort(data, data+len-1);
 179 }
 180
 181 #ifdef AAPL_NAMESPACE
 182 }
 183 #endif
 184
 185 #endif /* _AAPL_QUICKSORT_H */