シェルソート アルゴリズム間隔決め

Question

シェルソートを学習をしています
サイトで拾ってきたコードなんですがアルゴリズムの７，８行目のfor文が理解できません
間隔の決め方はh=h*3+1を満たす1,4,13,40,121...の中から要素数/9を超えない一番大きい
値を選ぶと学んだのですが,もし要素数が120個あるとして下のfor文だと間隔が4で決定してしまいませんか？
120/9だと13になるので1,4,13,40,121...のなかの13は超えていないので間隔は13になるとおもうのですが...

私の手順としては
１．h_tmpに1を入れ
２．条件式をおこない真なら下の処理h=h_tmpを行う
３.変化式？のh_tmp=h_tmp*3+1を行う
４再び条件式をおこなう

こんな感じです
手順が間違っているのでしょうか？
教えてください

コード
void shell_sort(int* array, size_t size)
{
    // 最初の間隔 h を決める
    // 1,4,13,40,121... のように、1 から始めて h=h*3+1 を満たす値を使う。
    // これらの値の中で、size / 9 を超えない一番大きい値を最初の h とする。
    size_t h = 1;
    for( size_t h_tmp = 1; h_tmp < size / 9; h_tmp = h_tmp * 3 + 1 ){
        h = h_tmp;
    }

    while( h > 0 ){
        for( size_t i = h; i < size; ++i ){
            int tmp = array[i];

            if( array[i-h] > tmp ){  // 挿入が必要か先に調べる
                size_t j = i;

                do {
                    array[j] = array[j-h];
                    j -= h;
                } while( j >= h && array[j-h] > tmp );

                array[j] = tmp;
            }
        }
        h /= 3;  // 間隔を縮める
    }
}

/
void shell_sort(int array, size_t size)
{
// 最初の間隔 h を決める
// 1,4,13,40,121... のように、1 から始めて h=h*3+1 を満たす値を使う。
// これらの値の中で、size / 9 を超えない一番大きい値を最初の h とする。
size_t h = 1;
for( size_t h_tmp = 1; h_tmp < size / 9; h_tmp = h_tmp * 3 + 1 ){
h = h_tmp;
}

while( h > 0 ){
    for( size_t i = h; i < size; ++i ){
        int tmp = array[i];

        if( array[i-h] > tmp ){  // 挿入が必要か先に調べる
            size_t j = i;

            do {
                array[j] = array[j-h];
                j -= h;
            } while( j >= h && array[j-h] > tmp );

            array[j] = tmp;
        }
    }
    h /= 3;  // 間隔を縮める
}

}

Answer 1

130/9だと13になるので

なりません。14.4444…を切り捨てて14です。

Comments

[sandalu]

回答ありがとうございます
要素数120でした
スミマセン

[maisumakun]

> 間隔の決め方はh=h*3+1を満たす1,4,13,40,121...の中から要素数/9を超えない一番大きい
値を選ぶと学んだのですが

決め方の流儀はいくつもありえます（このコードが別の流儀に従っていたのか、はたまた同じルールを意図して間違えたのかはわかりません）。

たとえ違うとり方になったとしても、最終的にはh=1で挿入ソートをすることになるので、ソートされることは間違いありません。

[sandalu]

そうなんですね

私の手順としては正しいということで大丈夫でしょうか？

[maisumakun]

> 下のfor文だと間隔が4で決定してしまいませんか？

そのとおりです。

[sandalu]

モヤモヤが晴れました
ありがとうございます