#include <generic_sort.h>
Inheritance diagram for generic_sort::
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) | |
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.
|
||||
|
|
|
||||
|
Definition at line 145 of file generic_sort.h. 00145 {}
|
|
||||
|
Definition at line 146 of file generic_sort.h. 00146 {}
|
|
||||||||
|
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.
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
|
|
||||||
|
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().
|
|
||||||
|
Definition at line 148 of file generic_sort.h. Referenced by histogram::calculate().
00149 {
00150 QuickSort(a, 0, N-1);
00151 } // sort
|
|
||||||||
|
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
|
1.2.8.1 written by Dimitri van Heesch,
© 1997-2001