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

generic_sort Class Template Reference

An abstract generic sort class. More...

#include <generic_sort.h>

Inheritance diagram for generic_sort::

dbl_sort List of all members.

Public Methods

 generic_sort ()
 ~generic_sort ()
void sort (T *a, size_t N)

Protected Methods

virtual int compare (T a, T b)=0
 This is an abstract function that should be defined by the class derived from generic_sort. More...


Private Methods

void swap (T *a, int i, int j)
 Exchange element a[i] and a[j]. More...

void QuickSort (T *a, int lo0, int hi0)
 This is a generic version of C.A.R Hoare's Quick Sort algorithm. More...

 generic_sort (const generic_sort &rhs)

Detailed Description

template<class T> class generic_sort

An abstract generic sort class.

This is an abstract class. The class that is derived from this class must define the compare function. The compare function returns an integer value that is less than, equal or greater than zero depending on the result of the comparision (the function is modeled after UNIX strcmp).

This class is based on the Java quicksort algorithm by James Gosling at at Sun Microsystems (see below).

QSortAlgorithm.java 1.3 29 Feb 1996 James Gosling

Copyright (c) 1994-1996 Sun Microsystems, Inc. All Rights Reserved.

Permission to use, copy, modify, and distribute this software and its documentation for NON-COMMERCIAL or COMMERCIAL purposes and without fee is hereby granted.

Please refer to the file http://www.javasoft.com/copy_trademarks.html for further important copyright and trademark information and to http://www.javasoft.com/licensing.html for further important licensing information for the Java (tm) Technology.

Definition at line 45 of file generic_sort.h.


Constructor & Destructor Documentation

template<class T>
generic_sort<T>::generic_sort<T> ( const generic_sort<T> & rhs ) [private]
 

template<class T>
generic_sort<T>::generic_sort<T> ( ) [inline]
 

Definition at line 145 of file generic_sort.h.

00145 {}

template<class T>
generic_sort<T>::~generic_sort<T> ( ) [inline]
 

Definition at line 146 of file generic_sort.h.

00146 {}


Member Function Documentation

template<class T>
void generic_sort<T>::QuickSort ( T * a,
int lo0,
int hi0 ) [inline, private]
 

This is a generic version of C.A.R Hoare's Quick Sort algorithm.

This will handle arrays that are already sorted, and arrays with duplicate keys.

If you think of a one dimensional array as going from the lowest index on the left to the highest index on the right then the parameters to this function are lowest index or left and highest index or right. The first time you call this function it will be with the parameters 0, a.length - 1.

Parameters:
a   an integer array
lo0   left boundary of array partition
hi0   right boundary of array partition

Definition at line 76 of file generic_sort.h.

Referenced by sort().

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

template<class T>
int generic_sort<T>::compare ( T a,
T b ) [protected, pure virtual]
 

This is an abstract function that should be defined by the class derived from generic_sort.

This function is passed two objects, a and b. It compares them and should return the following values:

    If (a == b) return 0
    if (a < b) return -1
    if (a > b) return 1

Referenced by QuickSort().

template<class T>
void generic_sort<T>::sort ( T * a,
size_t N ) [inline]
 

Definition at line 148 of file generic_sort.h.

Referenced by histogram::calculate().

00149   {
00150     QuickSort(a, 0, N-1);
00151   } // sort

template<class T>
void generic_sort<T>::swap ( T * a,
int i,
int j ) [inline, private]
 

Exchange element a[i] and a[j].

Definition at line 52 of file generic_sort.h.

Referenced by QuickSort().

00053   {
00054     T t;
00055 
00056     t = a[i];
00057     a[i] = a[j];
00058     a[j] = t;
00059   } // swap


The documentation for this class was generated from the following file:
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