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?

Why are you calling malloc anyway?

Why not do this.

Code:

---

static int ShellSortGaps[] = {
  1, 3, 7, // etc
};

---

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?

Doesn't matter.

You can make the array file scope (outside), or function scope (inside).

Even if it's inside, it's not initialised (or reinitialised) every time you call the function.

That seems to work really well, even as a “const static int”. Thank you.

Not sure whether const applies to pointer or to contents — would like both!

PS: I like the first line of your signature.

> Not sure whether const applies to pointer or to contents — would like both!
You can have either (or both)

Code:

---

// can change p, but not what it points at.
const int *p;
p = &foo;  // OK
p = &bar;  // OK
*p = 42;  // Bad

// can change what it points at, but not p itself
int * const p = &foo;
p = &bar;  // Bad
*p = 42;  // OK

// or both
const int * const p = &foo;
p = &bar;  // Bad
*p = 42;  // Bad

---