---

generic_sort.h

Go to the documentation of this file.

#ifndef _GENERIC_SORT_H_
#define _GENERIC_SORT_H_


template<class T>
class generic_sort
{

private:
  void swap(T *a, int i, int j)
  {
    T t;

    t = a[i];
    a[i] = a[j];
    a[j] = t;
  } // swap


  void QuickSort(T *a, int lo0, int hi0)
  {
    int lo = lo0;
    int hi = hi0;
    T mid;
    
    if ( hi0 > lo0) {
      /* Arbitrarily establishing partition element as the midpoint of
       * the array.
       */
      mid = a[ ( lo0 + hi0 ) / 2 ];
      
      // loop through the array until indices cross
      while( lo <= hi ) {
        /* find the first element that is greater than or equal to 
         * the partition element starting from the left Index.
         */
        while( ( lo < hi0 ) && ( compare(a[lo], mid) < 0 ) )
          ++lo;
        
        /* find an element that is smaller than or equal to 
         * the partition element starting from the right Index.
         */
        while( ( hi > lo0 ) && ( compare(a[hi], mid) > 0) )
          --hi;
        
        // if the indexes have not crossed, swap
        if( lo <= hi ) {
          swap(a, lo, hi);
          
          ++lo;
          --hi;
        }
      } // while
      
      /* If the right index has not reached the left side of array
       * must now sort the left partition.
       */
      if( lo0 < hi )
        QuickSort( a, lo0, hi );
      
      /* If the left index has not reached the right side of array
       * must now sort the right partition.
       */
      if( lo < hi0 )
        QuickSort( a, lo, hi0 );
      
    }
  }  // QuickSort

protected:
  virtual int compare( T a, T b) = 0;

private:
  generic_sort( const generic_sort &rhs );

public:
  generic_sort() {}
  ~generic_sort() {}

  void sort(T *a, size_t N)
  {
    QuickSort(a, 0, N-1);
  } // sort

}; // generic_sort

#endif

---