アルゴリズム(全101問中43問目)
No.43解説へ
次の手順はシェルソートによる整列を示している。データ列 7，2，8，3，1，9，4，5，6 を手順(1)～(4)に従って整列するとき，手順(3)を何回繰り返して完了するか。ここで，[ ]は小数点以下を切り捨てた結果を表す。
〔手順〕
〔手順〕
- [データ数÷3]→H とする。
- データ列を，互いにH要素分だけ離れた要素の集まりからなる部分列とし，それぞれの部分列を，挿入法を用いて整列する。
- [H÷3]→H とする。
- Hが0であればデータ列の整列は完了し，0でなければ(2)に戻る。
出典：平成24年春期 問 7
- 2
- 3
- 4
- 5
広告
解説
9つの要素を手順に沿って整列していくと、次のようになります。
- 9÷3 → H //H=3
- Hが3なので、要素ごとが互いに3つずつ離れた要素から成る3つの部分列に分解し、それぞれを整列する。
- 3÷3 → H //H=1、(3)の処理1回目
- Hが0ではないので、(2)の処理に戻る
- Hが1なので、要素ごとが互いに1つずつ離れた要素から成る 3,1,6,4,2,8,7,5,9 を整列し、1,2,3,4,5,6,7,8,9 とする。
- 1÷3 → H //H=0、(3)の処理2回目
- Hが0なので、データ列の整列が完了
広告