Thread: int static const *

ShellSort is good. And I have a strong view about optimal gaps: start 1, 3, then closest to immediately previous * Sqrt5 that is coprime to all smaller. It would be nice to have a static const int *, pre-defined. What I’m doing is

Code:

/*
   ShellSort is very fast at short arrays, but QuickSort's segregation helps multi-CPU with long arrays.
   Included are gaps up to C's max integer = 2^31 - 1, subsequent being commented out.
   From http://en.wikipedia.org/wiki/Shellsort
      > Gonnet and Baeza-Yates observed that Shellsort makes the fewest comparisons on average when the ratios of successive
      > gaps are roughly equal to 2.2. This is why their sequence with ratio 2.2 and Tokuda's sequence with ratio 2.25
      > prove efficient. However, it is not known why this is so. Sedgewick recommends using gaps which have low greatest
      > common divisors or are pairwise coprime.
   So, start 1, 3, then closest to immediately previous * Sqrt5 that is coprime to all smaller
    ==> ratios tend to ~=2.236.
   Gap >=83 ==> ratio within -0.0242% to +1.7% of Sqrt5.
*/


static double tolerance;


inline _Bool rhombiiGt(const Rhombus* const rhP0, const Rhombus* const rhP1)
{
   // [blah, using tolerance]
}  // rhombiiGt


static int* ShellSortGaps;


void ShellSort(struct Rhombus *rhombii, int n, const double tol)
{
   int intervalNum, interval, i, j;
   struct Rhombus rh;


   tolerance = tol;


   if( NULL == ShellSortGaps )
   {
      ShellSortGaps = malloc( sizeof(int) * 27 );
      ShellSortGaps[ 0] =          1 ;
      ShellSortGaps[ 1] =          3 ;
      ShellSortGaps[ 2] =          7 ;
      ShellSortGaps[ 3] =         16 ;
      ShellSortGaps[ 4] =         37 ;
      ShellSortGaps[ 5] =         83 ;
      ShellSortGaps[ 6] =        187 ;
      ShellSortGaps[ 7] =        419 ;
      ShellSortGaps[ 8] =        937 ;
      ShellSortGaps[ 9] =       2099 ;
      ShellSortGaps[10] =       4693 ;
      ShellSortGaps[11] =      10499 ;
      ShellSortGaps[12] =      23479 ;
      ShellSortGaps[13] =      52501 ;
      ShellSortGaps[14] =     117391 ;
      ShellSortGaps[15] =     262495 ;
      ShellSortGaps[16] =     586961 ;
      ShellSortGaps[17] =    1312481 ;
      ShellSortGaps[18] =    2934793 ;
      ShellSortGaps[19] =    6562397 ;
      ShellSortGaps[20] =   14673961 ;
      ShellSortGaps[21] =   32811973 ;
      ShellSortGaps[22] =   73369801 ;
      ShellSortGaps[23] =  164059859 ;
      ShellSortGaps[24] =  366848983 ;
      ShellSortGaps[25] =  820299269 ;
      ShellSortGaps[26] = 1834244921 ;  // Below 2^31 ~= 2 billion
      /*
         4101496331, 9171224603, 20507481647, 45856123009, 102537408229, 229280615033, 512687041133, 1146403075157, 2563435205663,
         5732015375783, 12817176028331, 28660076878933, 64085880141667, 143300384394667, 320429400708323, 716501921973329,
         1602147003541613, 3582509609866643, 8010735017708063,  // Excel's integers misbehave after 1 quadrillion
         17912548049333207, 40053675088540303, 89562740246666023, 200268375442701509, 447813701233330109,
         1001341877213507537, 2239068506166650537, 5006709386067537661, 11195342530833252689  // Below 2^64 ~= 18 quintillion
      */
   }  // NULL == ShellSortGaps


   for(intervalNum = 0;  intervalNum < 27 &&  ShellSortGaps[intervalNum] <= n ;  intervalNum++)
      ;
   intervalNum--;


   // Based on Algorithms in C (1990), Robert Segdewick, p109
   for( ; intervalNum >= 0 ; intervalNum-- )
   {
      interval = ShellSortGaps[intervalNum];
      for(i = interval+1 ; i <= n ; i+= interval)
      {
         rh = rhombii[i];
         j = i;
         while( j > interval  &&  rhombiiGt(rhombii + (j - interval), &rh) )
         {
            rhombii[j] = rhombii[j - interval];
            j -= interval;
         }  // j loop
         rhombii[j] = rh;
      }  // i loop
   } // intervalNum,interval loop
}  // ShellSort

The population of the array is nasty nasty! Is there en elegant way to define, and allocate the memory for, the ShellSortGaps array of gaps?

In the function, or outside?

If inside, would the assignment be executed every invocation of the function, even if sorting an array of tiny length?