libcoyotl - A Library of C++ Tools

Created by Scott Robert Ladd at Coyote Gulch Productions.


sortutil.h
00001 //---------------------------------------------------------------------
00002 //  Algorithmic Conjurings @ http://www.coyotegulch.com
00003 //
00004 //  sortutil.h
00005 //
00006 //  Generic tools for sorting C-type arrays of data.
00007 //---------------------------------------------------------------------
00008 //
00009 //  Copyright 1990-2005 Scott Robert Ladd
00010 //
00011 //  This program is free software; you can redistribute it and/or modify
00012 //  it under the terms of the GNU General Public License as published by
00013 //  the Free Software Foundation; either version 2 of the License, or
00014 //  (at your option) any later version.
00015 //  
00016 //  This program is distributed in the hope that it will be useful,
00017 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
00018 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00019 //  GNU General Public License for more details.
00020 //  
00021 //  You should have received a copy of the GNU General Public License
00022 //  along with this program; if not, write to the
00023 //      Free Software Foundation, Inc.
00024 //      59 Temple Place - Suite 330
00025 //      Boston, MA 02111-1307, USA.
00026 //
00027 //-----------------------------------------------------------------------
00028 //
00029 //  For more information on this software package, please visit
00030 //  Scott's web site, Coyote Gulch Productions, at:
00031 //
00032 //      http://www.coyotegulch.com
00033 //  
00034 //-----------------------------------------------------------------------
00035 
00036 #if !defined(LIBCOYOTL_SORTUTIL_H)
00037 #define LIBCOYOTL_SORTUTIL_H
00038 
00039 #include <stdexcept>
00040 
00041 #include <climits>
00042 
00043 namespace libcoyotl
00044 {
00045 
00046     //--------------------------------------------------
00047     // sort two items
00048     
00049     template<class  T>
00050     inline void sort_two(T & a, T & b)
00051     {
00052         if (a > b)
00053         {
00054             T t = a;
00055             a = b;
00056             b = t;
00057         }
00058     }
00059     
00060     //--------------------------------------------------
00061     // sort three items
00062     
00063     template<class  T>
00064     inline void sort_three(T & a, T & b, T & c)
00065     {
00066         sort_two(a,b);
00067         sort_two(a,c);
00068         sort_two(b,c);
00069     }
00070     
00071     //--------------------------------------------------
00072     // shell sort an array in ascending order
00073     
00074     template<class  T> void
00075     shell_sort(T * a, size_t n)
00076     {
00077         size_t inc, i, j;
00078         T t;
00079         
00080         // algorithm relies on one-based arrays
00081         --a;
00082         
00083         for (inc = 1; inc <= n / 9; inc = 3 * inc + 1) ;
00084         
00085         for ( ; inc > 0; inc /= 3)
00086         {
00087             for (i = inc + 1; i <= n; i += inc)
00088             {
00089                 t = a[i];
00090                 j = i;
00091                 
00092                 while ((j > inc) && (a[j - inc] > t))
00093                 {
00094                     a[j] = a[j - inc];
00095                     j -= inc;
00096                 }
00097                 
00098                 a[j] = t;
00099             }
00100         }
00101     }
00102     
00103     //--------------------------------------------------
00104     // shell sort an array in ascending order
00105     
00106     template<class  T>
00107     void shell_sort_descending(T * array, size_t n)
00108     {
00109         size_t increment, i, j;
00110         T t;
00111         
00112         // algorithm relies on one-based arrays
00113         --array;
00114         
00115         for (increment = 1; increment <= n / 9; increment = 3 * increment + 1) ;
00116         
00117         for ( ; increment > 0; increment /= 3)
00118         {
00119             for (i = increment + 1; i <= n; i += increment)
00120             {
00121                 t = array[i];
00122                 j = i;
00123                 
00124                 while ((j > increment) && (array[j - increment] < t))
00125                 {
00126                     array[j] = array[j - increment];
00127                     j -= increment;
00128                 }
00129                 
00130                 array[j] = t;
00131             }
00132         }
00133     }
00134     
00135     //--------------------------------------------------
00136     // Quick Sort an array in ascending order
00137     template <class T>
00138     void quick_sort(T * array, size_t n)
00139     {
00140         static const size_t STACK_SIZE = CHAR_BIT * sizeof(int);
00141         static const size_t THRESHOLD  = 7;
00142 
00143         size_t left_index  = 0;
00144         size_t right_index = n - 1;
00145 
00146         T temp, pivot;
00147         size_t scan_left, scan_right, middle, pivot_index, size_left, size_right;
00148         size_t stack_left[STACK_SIZE], stack_right[STACK_SIZE], stack_ptr = 0;
00149         
00150         while (true)
00151         {
00152             while (right_index > left_index)
00153             {
00154                 if ((right_index - left_index) > THRESHOLD)
00155                 {
00156                     // "median-of-three" partitioning
00157                     middle = (left_index + right_index) / 2;
00158                     
00159                     // three-sort left, middle, and right elements
00160                     if (array[left_index] > array[middle])
00161                     {
00162                         temp              = array[left_index];
00163                         array[left_index] = array[middle];
00164                         array[middle]     = temp;
00165                     }
00166                     
00167                     if (array[left_index] > array[right_index])
00168                     {
00169                         temp               = array[left_index];
00170                         array[left_index]  = array[right_index];
00171                         array[right_index] = temp;
00172                     }
00173                     
00174                     if (array[middle] > array[right_index])
00175                     {
00176                         temp               = array[middle];
00177                         array[middle]      = array[right_index];
00178                         array[right_index] = temp;
00179                     }
00180                     
00181                     pivot_index = right_index - 1;
00182                     
00183                     temp               = array[middle];
00184                     array[middle]      = array[pivot_index];
00185                     array[pivot_index] = temp;
00186                     
00187                     // set-up for partitioning
00188                     scan_left  = left_index  + 1;
00189                     scan_right = right_index - 2;
00190                 }
00191                 else
00192                 {
00193                     pivot_index = right_index;
00194                     scan_left   = left_index;
00195                     scan_right  = right_index - 1;
00196                 }
00197                 
00198                 pivot = array[pivot_index];
00199                 
00200                 while (true)
00201                 {
00202                     // scan from left
00203                     while ((array[scan_left] < pivot) && (scan_left < right_index))
00204                         ++scan_left;
00205                     
00206                     // scan from right
00207                     while ((array[scan_right] > pivot) && (scan_right > left_index))
00208                         --scan_right;
00209                     
00210                     // if scans have met, exit inner loop
00211                     if (scan_left >= scan_right)
00212                         break;
00213                     
00214                     // exchange elements
00215                     temp              = array[scan_right];
00216                     array[scan_right] = array[scan_left];
00217                     array[scan_left]  = temp;
00218                     
00219                     if (scan_left < right_index)
00220                         ++scan_left;
00221 
00222                     if (scan_right > left_index)
00223                         --scan_right;
00224                 }
00225                 
00226                 // exchange final element
00227                 if (scan_left != pivot_index)
00228                 {
00229                     temp               = array[pivot_index];
00230                     array[pivot_index] = array[scan_left];
00231                     array[scan_left]   = temp;
00232                 }
00233                 
00234                 // place largest partition on stack
00235                 size_left  = scan_left   - left_index;
00236                 size_right = right_index - scan_left;
00237                 
00238                 if (size_left > size_right)
00239                 {
00240                     if (size_left != 1)
00241                     {
00242                         ++stack_ptr;
00243                         
00244                         if (stack_ptr == STACK_SIZE)
00245                             throw std::runtime_error("stack overflow in quick_sort");
00246                         
00247                         stack_left[stack_ptr]  = left_index;
00248                         stack_right[stack_ptr] = scan_left - 1;
00249                     }
00250                     
00251                     if (size_right != 0)
00252                         left_index = scan_left + 1;
00253                     else
00254                         break;
00255                 }
00256                 else
00257                 {
00258                     if (size_right != 1)
00259                     {
00260                         ++stack_ptr;
00261                         
00262                         if (stack_ptr == STACK_SIZE)
00263                             throw std::runtime_error("stack overflow in quick_sort");
00264                         
00265                         stack_left[stack_ptr]  = scan_left + 1;
00266                         stack_right[stack_ptr] = right_index;
00267                     }
00268                     
00269                     if (size_left != 0)
00270                         right_index = scan_left - 1;
00271                     else
00272                         break;
00273                 }
00274             }
00275             
00276             // iterate with values from stack
00277             if (stack_ptr > 0)
00278             {
00279                 left_index  = stack_left[stack_ptr];
00280                 right_index = stack_right[stack_ptr];
00281                 
00282                 --stack_ptr;
00283             }
00284             else
00285                 break;
00286         }
00287     }
00288             
00289 } // end namespace libcoyotl
00290 
00291 #endif
00292 

© 1996-2005 Scott Robert Ladd. All rights reserved.
HTML documentation generated by Dimitri van Heesch's excellent Doxygen tool.