Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

Sort.h

Go to the documentation of this file.
00001 
00002 #ifndef __Sort_hh__
00003 #define __Sort_hh__
00004 
00005 
00006 //
00007 // A fast in-place sorting routine that can be customized to a
00008 // specific type with all swap and compare operations inlined.
00009 //
00010 // For arrays of types for which assignment, > and < exist (such as
00011 // int,float,etc. or appropriately-defined user types), the usage is
00012 // simple:
00013 //
00014 //   double* a = new double [100];
00015 //   sort(a,100);
00016 // 
00017 // This will sort the array into increasing order.  To sort in another
00018 // order, or to sort more complex types, you must provide compare and
00019 // swap routines:
00020 //
00021 //   sortSwap(cl,i,j) 
00022 //      - Swap elements i and j.
00023 //
00024 //   sortCmp(cl,i,j) 
00025 //      - Compare elements i and j, returning -1,0,1 for <,=,>.
00026 // 
00027 // The argument 'cl' is a closure.  Note that the sorting routine does
00028 // not evaluate cl in any context other than these two routines.
00029 //
00030 // The postcondition of sort() is (sortCmp(cl,i,j) <= 0) for 
00031 // all 0 <= i < j < n, i.e. increasing order.
00032 //
00033 // Here is an example of how to sort an array of points by x
00034 // coordinate in decreasing order:
00035 //
00036 // struct Point { int x, y; };
00037 // static inline void sortSwap (Point* a, int i, int j) {
00038 //      swap(a[i],a[j]);
00039 // }
00040 // static inline int sortCmp (Point* a, int i, int j) {
00041 //      return a[j].x - a[i].x;
00042 // }
00043 // Point* points = new Point [100];
00044 // sort(points,100);
00045 //
00046 
00047 // Copyright (C) 2002 David R. Martin <dmartin@eecs.berkeley.edu>
00048 //
00049 // This program is free software; you can redistribute it and/or
00050 // modify it under the terms of the GNU General Public License as
00051 // published by the Free Software Foundation; either version 2 of the
00052 // License, or (at your option) any later version.
00053 // 
00054 // This program is distributed in the hope that it will be useful, but
00055 // WITHOUT ANY WARRANTY; without even the implied warranty of
00056 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00057 // General Public License for more details.
00058 // 
00059 // You should have received a copy of the GNU General Public License
00060 // along with this program; if not, write to the Free Software
00061 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
00062 // 02111-1307, USA, or see http://www.gnu.org/copyleft/gpl.html.
00063 
00064 #include <assert.h>
00065 
00066 // Public routines for sorting arrays of simple values that have
00067 // assignment, < and > defined.
00068 template <class T>
00069 static inline void sortSwap (T* a, int i, int j) {
00070     T tmp = a[i]; a[i] = a[j]; a[j] = tmp;
00071 }
00072 template <class T>
00073 static inline int sortCmp (T* a, int i, int j) {
00074     if (a[i] < a[j]) { return -1; }
00075     if (a[i] > a[j]) { return 1; }
00076     return 0;
00077 }
00078 
00079 // Private routine.
00080 // Sort elements [start,start+n) using insertion sort.
00081 template <class Closure>
00082 inline void
00083 __insertionSort (Closure cl, int start, int n)
00084 {
00085     for (int i = start; i < start+n-1; i++) {
00086         for (int j = i+1; j > start; j--) {
00087             if (sortCmp(cl,j-1,j) <= 0) { break; }
00088             sortSwap(cl,j-1,j);
00089         }
00090     }
00091 }
00092 
00093 // Private routine.
00094 // Sort elements [start,start+n) using selection sort.
00095 template <class Closure>
00096 inline void
00097 __selectionSort1 (Closure cl, int start, int n)
00098 {
00099     for (int i = start; i < start + n - 1; i++) {
00100         // Skip over duplicate elements.
00101         if (i > start && sortCmp(cl,i,i-1) == 0) { continue; }
00102         // Find the smallest element in [i,end] and move it to the front.
00103         int minLoc = i;
00104         for (int j = i + 1; j < start + n; j++) {
00105             if (sortCmp(cl,j,minLoc) < 0) {
00106                 minLoc = j;
00107             }
00108         }
00109         if (minLoc > i) {
00110             sortSwap (cl, i, minLoc);
00111         }
00112     }
00113 }
00114 
00115 // Private routine.
00116 // Sort elements [start,start+n) using double-ended selection sort.
00117 template <class Closure>
00118 inline void
00119 __selectionSort2 (Closure cl, int start, int n)
00120 {
00121     int i = start;
00122     int j = start + n - 1;
00123     while (i < j) {
00124         // Skip over duplicate elements.
00125         if (i > start && sortCmp(cl,i,i-1) == 0) { i++; continue; }
00126         if (j < start+n-1 && sortCmp(cl,j,j+1) == 0) { j--; continue; }
00127         // Find the min and max elements in [i,j].
00128         int minLoc=i, maxLoc=i;
00129         for (int k = i + 1; k <= j; k++) {
00130             if (sortCmp(cl,k,minLoc) < 0) { minLoc = k; }
00131             if (sortCmp(cl,k,maxLoc) > 0) { maxLoc = k; }
00132         }
00133         // Move the min element to the front and the max element to
00134         // the back.
00135         if (minLoc == maxLoc) { break; }
00136         if (minLoc > maxLoc) { 
00137             sortSwap(cl,minLoc,maxLoc); 
00138             int tmp=minLoc; minLoc=maxLoc; maxLoc=tmp;
00139         }
00140         if (minLoc > i) { sortSwap(cl,i,minLoc); }
00141         if (maxLoc < j) { sortSwap(cl,j,maxLoc); }
00142         i++; j--;
00143     }
00144 }
00145 
00146 // Private routine.
00147 // Return the median of the 3 arguments as defined by cmp##NAME.
00148 // Used internally in qsort to pick a pivot.
00149 template <class Closure>
00150 inline int 
00151 __3median (Closure cl, int x, int y, int z) 
00152 {
00153     return sortCmp(cl,x,y) > 0 
00154                 ? (sortCmp(cl,y,z) > 0 
00155                         ? y : (sortCmp(cl,x,z) > 0 ? z : x)) 
00156                 : (sortCmp(cl,y,z) < 0 
00157                         ? y : (sortCmp(cl,x,z) < 0 ? z : x));
00158 }
00159 
00160 // Private routine.
00161 // Sort elements [start,start+n) using quick sort.
00162 template <class Closure>
00163 inline void
00164 __quickSort (Closure cl, int start, int n)
00165 {
00166     // Use selection-sort for small arrays.
00167     if (n < 16) { 
00168         __insertionSort (cl, start, n); 
00169         //__selectionSort1 (cl, start, n); 
00170         //__selectionSort2 (cl, start, n); 
00171         return; 
00172     }
00173 
00174     // Pick the median of elements n/4, n/2, 3n/4 as the pivot, and
00175     // move it to the front.
00176     int x = start + (n >> 2);
00177     int y = start + (n >> 1);
00178     int z = x + (n >> 1);
00179     int pivotLoc = __3median (cl, x, y, z);
00180     sortSwap (cl, start, pivotLoc);
00181 
00182     // Segregate array elements into three groups.  Those equal to the
00183     // pivot (=), those less than the pivot (<), and those greater
00184     // than the pivot (>).  After this loop, the array will look like
00185     // this:
00186     //          S   P    RL                                                     
00187     //          =====<<<<<>>>>>                                                 
00188     //
00189     // Where S=start P=pivot R=right L=left.                            
00190     //
00191     int pivot = start;
00192     int left = start + 1;
00193     int right = start + n - 1;
00194     while (1) {
00195       restart:
00196         while (left <= right) {
00197             int c = sortCmp (cl, left, pivot);
00198             if (c > 0) { break; }
00199             if (c < 0) { left++; continue; }
00200             if (left != pivot+1) { sortSwap (cl, left, pivot+1); }
00201             pivot++; left++;
00202         }
00203         while (left <= right) {
00204             int c = sortCmp (cl, right, pivot);
00205             if (c < 0) { break; }
00206             if (c > 0) { right--; continue; }
00207 #ifdef __DEBUG__            
00208             assert (left < right);
00209 #endif            
00210             sortSwap (cl, left, right);
00211             if (left != pivot+1) { sortSwap (cl, left, pivot+1); }
00212             pivot++; left++; right--;
00213             goto restart;
00214         }
00215         if (left > right) { break; }
00216         sortSwap (cl, left, right);
00217     }
00218     
00219 #ifdef __DEBUG__            
00220     assert (pivot >= start);
00221     assert (right >= pivot);
00222     assert (left == right + 1);
00223     assert (left <= start + n);
00224 #endif
00225     int numEq = pivot - start + 1;
00226     int numLt = right - pivot;
00227     int numLe = left - start;
00228     int numGt = n - numLe;
00229     
00230 #ifdef __DEBUG__            
00231     assert (numEq + numLt + numGt == n);
00232 #endif
00233     // Copy pivot values into middle.                                   
00234     int count = (numEq < numLt) ? numEq : numLt;
00235     int dist = numLe - count;
00236     for (int i = 0; i < count; i++) {
00237         sortSwap (cl, start + i, start + i + dist); 
00238     }
00239 
00240     // Recursively sort the < and > chunks.                             
00241     if (numLt > 0) { __quickSort (cl, start, numLt); }
00242     if (numGt > 0) { __quickSort (cl, left, numGt); }
00243 }
00244 
00245 // Public sort routine.
00246 template <class Closure>
00247 inline void
00248 sort (Closure cl, int n)
00249 {
00250     __quickSort (cl, 0, n);
00251 #ifdef __DEBUG__    
00252     // Check the postcondition.
00253     for (int i = 1; i < n; i++) { 
00254         assert (sortCmp (cl, i-1, i) <= 0); 
00255     } 
00256 #endif
00257 
00258 }
00259 
00260 #endif // __Sort_hh__

Generated on Tue Mar 24 16:14:02 2009 for DENDRO by  doxygen 1.3.9.1