質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
基本情報技術者

基本情報技術者とは、経済産業省が行う国家資格「情報処理技術者試験」の区分の一つです。試験ではプログラマーやシステムエンジニアなどIT業界で働くために必要とされる基礎知識や情報処理において論理的な考え方ができるか等が問われ、企業から高い評価を獲ることができ、IT業界の入門的な資格として人気があります。

Q&A

解決済

1回答

1452閲覧

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

sandalu

総合スコア4

基本情報技術者

基本情報技術者とは、経済産業省が行う国家資格「情報処理技術者試験」の区分の一つです。試験ではプログラマーやシステムエンジニアなどIT業界で働くために必要とされる基礎知識や情報処理において論理的な考え方ができるか等が問われ、企業から高い評価を獲ることができ、IT業界の入門的な資格として人気があります。

0グッド

0クリップ

投稿2021/01/24 10:17

編集2021/01/24 11:05

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

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

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

コード 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; // 間隔を縮める }

}

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

130/9だと13になるので

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

投稿2021/01/24 11:03

maisumakun

総合スコア145121

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

sandalu

2021/01/24 11:07 編集

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

2021/01/24 11:13 編集

> 間隔の決め方はh=h*3+1を満たす1,4,13,40,121...の中から要素数/9を超えない一番大きい 値を選ぶと学んだのですが 決め方の流儀はいくつもありえます(このコードが別の流儀に従っていたのか、はたまた同じルールを意図して間違えたのかはわかりません)。 たとえ違うとり方になったとしても、最終的にはh=1で挿入ソートをすることになるので、ソートされることは間違いありません。
sandalu

2021/01/24 11:50

そうなんですね 私の手順としては正しいということで大丈夫でしょうか?
maisumakun

2021/01/24 11:52

> 下のfor文だと間隔が4で決定してしまいませんか? そのとおりです。
sandalu

2021/01/24 11:56

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問