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

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