Main Page   Namespace List   Class Hierarchy   Compound List   File List   Compound Members   File Members

# generic_sort.h

Go to the documentation of this file.
00001
00002 #ifndef _GENERIC_SORT_H_
00003 #define _GENERIC_SORT_H_
00004
00043
00044 template<class T>
00045 class generic_sort
00046 {
00047
00048 private:
00052   void swap(T *a, int i, int j)
00053   {
00054     T t;
00055
00056     t = a[i];
00057     a[i] = a[j];
00058     a[j] = t;
00059   } // swap
00060
00061
00076   void QuickSort(T *a, int lo0, int hi0)
00077   {
00078     int lo = lo0;
00079     int hi = hi0;
00080     T mid;
00081
00082     if ( hi0 > lo0) {
00083       /* Arbitrarily establishing partition element as the midpoint of
00084        * the array.
00085        */
00086       mid = a[ ( lo0 + hi0 ) / 2 ];
00087
00088       // loop through the array until indices cross
00089       while( lo <= hi ) {
00090         /* find the first element that is greater than or equal to
00091          * the partition element starting from the left Index.
00092          */
00093         while( ( lo < hi0 ) && ( compare(a[lo], mid) < 0 ) )
00094           ++lo;
00095
00096         /* find an element that is smaller than or equal to
00097          * the partition element starting from the right Index.
00098          */
00099         while( ( hi > lo0 ) && ( compare(a[hi], mid) > 0) )
00100           --hi;
00101
00102         // if the indexes have not crossed, swap
00103         if( lo <= hi ) {
00104           swap(a, lo, hi);
00105
00106           ++lo;
00107           --hi;
00108         }
00109       } // while
00110
00111       /* If the right index has not reached the left side of array
00112        * must now sort the left partition.
00113        */
00114       if( lo0 < hi )
00115         QuickSort( a, lo0, hi );
00116
00117       /* If the left index has not reached the right side of array
00118        * must now sort the right partition.
00119        */
00120       if( lo < hi0 )
00121         QuickSort( a, lo, hi0 );
00122
00123     }
00124   }  // QuickSort
00125
00126 protected:
00139   virtual int compare( T a, T b) = 0;
00140
00141 private:
00142   generic_sort( const generic_sort &rhs );
00143
00144 public:
00145   generic_sort() {}
00146   ~generic_sort() {}
00147
00148   void sort(T *a, size_t N)
00149   {
00150     QuickSort(a, 0, N-1);
00151   } // sort
00152
00153 }; // generic_sort
00154
00155 #endif

Generated at Wed May 21 21:19:26 2003 for Basic Statistics Functions by 1.2.8.1 written by Dimitri van Heesch, © 1997-2001