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 Thu May 22 21:12:35 2003 for Hurst Exponent Calculation and Supporting Statistics by doxygen1.2.8.1 written by Dimitri van Heesch, © 1997-2001