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 <climits>
00040 #include <stdexcept>
00041 
00042 namespace libcoyotl
00043 {
00044 
00045     //--------------------------------------------------
00046     // sort two items
00047     
00048     template<class  T>
00049     inline void sort_two(T & a, T & b)
00050     {
00051         if (a > b)
00052         {
00053             T t = a;
00054             a = b;
00055             b = t;
00056         }
00057     }
00058     
00059     //--------------------------------------------------
00060     // sort three items
00061     
00062     template<class  T>
00063     inline void sort_three(T & a, T & b, T & c)
00064     {
00065         sort_two(a,b);
00066         sort_two(a,c);
00067         sort_two(b,c);
00068     }
00069     
00070     //--------------------------------------------------
00071     // shell sort an array in ascending order
00072     
00073     template<class  T> void
00074     shell_sort(T * a, size_t n)
00075     {
00076         size_t inc, i, j;
00077         T t;
00078         
00079         // algorithm relies on one-based arrays
00080         --a;
00081         
00082         for (inc = 1; inc <= n / 9; inc = 3 * inc + 1) ;
00083         
00084         for ( ; inc > 0; inc /= 3)
00085         {
00086             for (i = inc + 1; i <= n; i += inc)
00087             {
00088                 t = a[i];
00089                 j = i;
00090                 
00091                 while ((j > inc) && (a[j - inc] > t))
00092                 {
00093                     a[j] = a[j - inc];
00094                     j -= inc;
00095                 }
00096                 
00097                 a[j] = t;
00098             }
00099         }
00100     }
00101     
00102     //--------------------------------------------------
00103     // shell sort an array in ascending order
00104     
00105     template<class  T>
00106     void shell_sort_descending(T * array, size_t n)
00107     {
00108         size_t increment, i, j;
00109         T t;
00110         
00111         // algorithm relies on one-based arrays
00112         --array;
00113         
00114         for (increment = 1; increment <= n / 9; increment = 3 * increment + 1) ;
00115         
00116         for ( ; increment > 0; increment /= 3)
00117         {
00118             for (i = increment + 1; i <= n; i += increment)
00119             {
00120                 t = array[i];
00121                 j = i;
00122                 
00123                 while ((j > increment) && (array[j - increment] < t))
00124                 {
00125                     array[j] = array[j - increment];
00126                     j -= increment;
00127                 }
00128                 
00129                 array[j] = t;
00130             }
00131         }
00132     }
00133     
00134     //--------------------------------------------------
00135     // Quick Sort an array in ascending order
00136     template <class T>
00137     void quick_sort(T * array, size_t n)
00138     {
00139         static const size_t STACK_SIZE = CHAR_BIT * sizeof(int);
00140         static const size_t THRESHOLD  = 7;
00141 
00142         size_t left_index  = 0;
00143         size_t right_index = n - 1;
00144 
00145         T temp, pivot;
00146         size_t scan_left, scan_right, middle, pivot_index, size_left, size_right;
00147         size_t stack_left[STACK_SIZE], stack_right[STACK_SIZE], stack_ptr = 0;
00148         
00149         while (true)
00150         {
00151             while (right_index > left_index)
00152             {
00153                 if ((right_index - left_index) > THRESHOLD)
00154                 {
00155                     // "median-of-three" partitioning
00156                     middle = (left_index + right_index) / 2;
00157                     
00158                     // three-sort left, middle, and right elements
00159                     if (array[left_index] > array[middle])
00160                     {
00161                         temp              = array[left_index];
00162                         array[left_index] = array[middle];
00163                         array[middle]     = temp;
00164                     }
00165                     
00166                     if (array[left_index] > array[right_index])
00167                     {
00168                         temp               = array[left_index];
00169                         array[left_index]  = array[right_index];
00170                         array[right_index] = temp;
00171                     }
00172                     
00173                     if (array[middle] > array[right_index])
00174                     {
00175                         temp               = array[middle];
00176                         array[middle]      = array[right_index];
00177                         array[right_index] = temp;
00178                     }
00179                     
00180                     pivot_index = right_index - 1;
00181                     
00182                     temp               = array[middle];
00183                     array[middle]      = array[pivot_index];
00184                     array[pivot_index] = temp;
00185                     
00186                     // set-up for partitioning
00187                     scan_left  = left_index  + 1;
00188                     scan_right = right_index - 2;
00189                 }
00190                 else
00191                 {
00192                     pivot_index = right_index;
00193                     scan_left   = left_index;
00194                     scan_right  = right_index - 1;
00195                 }
00196                 
00197                 pivot = array[pivot_index];
00198                 
00199                 while (true)
00200                 {
00201                     // scan from left
00202                     while ((array[scan_left] < pivot) && (scan_left < right_index))
00203                         ++scan_left;
00204                     
00205                     // scan from right
00206                     while ((array[scan_right] > pivot) && (scan_right > left_index))
00207                         --scan_right;
00208                     
00209                     // if scans have met, exit inner loop
00210                     if (scan_left >= scan_right)
00211                         break;
00212                     
00213                     // exchange elements
00214                     temp              = array[scan_right];
00215                     array[scan_right] = array[scan_left];
00216                     array[scan_left]  = temp;
00217                     
00218                     if (scan_left < right_index)
00219                         ++scan_left;
00220 
00221                     if (scan_right > left_index)
00222                         --scan_right;
00223                 }
00224                 
00225                 // exchange final element
00226                 if (scan_left != pivot_index)
00227                 {
00228                     temp               = array[pivot_index];
00229                     array[pivot_index] = array[scan_left];
00230                     array[scan_left]   = temp;
00231                 }
00232                 
00233                 // place largest partition on stack
00234                 size_left  = scan_left   - left_index;
00235                 size_right = right_index - scan_left;
00236                 
00237                 if (size_left > size_right)
00238                 {
00239                     if (size_left != 1)
00240                     {
00241                         ++stack_ptr;
00242                         
00243                         if (stack_ptr == STACK_SIZE)
00244                             throw std::runtime_error("stack overflow in quick_sort");
00245                         
00246                         stack_left[stack_ptr]  = left_index;
00247                         stack_right[stack_ptr] = scan_left - 1;
00248                     }
00249                     
00250                     if (size_right != 0)
00251                         left_index = scan_left + 1;
00252                     else
00253                         break;
00254                 }
00255                 else
00256                 {
00257                     if (size_right != 1)
00258                     {
00259                         ++stack_ptr;
00260                         
00261                         if (stack_ptr == STACK_SIZE)
00262                             throw std::runtime_error("stack overflow in quick_sort");
00263                         
00264                         stack_left[stack_ptr]  = scan_left + 1;
00265                         stack_right[stack_ptr] = right_index;
00266                     }
00267                     
00268                     if (size_left != 0)
00269                         right_index = scan_left - 1;
00270                     else
00271                         break;
00272                 }
00273             }
00274             
00275             // iterate with values from stack
00276             if (stack_ptr > 0)
00277             {
00278                 left_index  = stack_left[stack_ptr];
00279                 right_index = stack_right[stack_ptr];
00280                 
00281                 --stack_ptr;
00282             }
00283             else
00284                 break;
00285         }
00286     }
00287             
00288 } // end namespace libcoyotl
00289 
00290 #endif
00291 

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