アルゴリズム (全82問中51問目)

No.51

次の手順はシェルソートによる整列を示している。データ列7,2,8,3,1,9,4,5,6を手順(1)〜(4)に従って整列するとき,手順(3)を何回繰り返して完了するか。
 ここで,[ ]は小数点以下を切り捨てた結果を表す。

〔手順〕
  • [データ数÷3]→H とする。
  • データ列を,互いにH要素分だけ離れた要素の集まりからなる部分列とし,それぞれの部分列を,挿入法を用いて整列する。
  • [H÷3]→H とする。
  • Hが0であればデータ列の整列は完了し, 0でなければ(2)に戻る。
  • [この問題の出題歴]
  • 応用情報技術者 H24春期 問7
  • ソフトウェア開発技術者 H16春期 問11

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

手順に沿って整列を行うと次のようになります。
  • H←9÷3=3
  • 要素ごとが互いに3つずつ離れた要素から成る3つの部分文字列に分解し、それぞれ整列を行います。
    • [部分列1] 7,3,4 →(整列)→ 3,4,7
    • [部分列2] 2,1,5 →(整列)→ 1,2,5
    • [部分列3] 8,9,6 →(整列)→ 6,8,9
    10.gif/image-size:297×163
  • H←3÷3=1 //1回目
  • H≠0なので2に戻る
  • 要素ごとが互いに1つずつ離れた要素から成る3,4,7,1,2,5,6,8,9を整列し、1,2,3,4,5,6,7,8,9 とします。
  • H←1÷3=0(小数点未満切り捨て) //2回目
この時点でHが0になるためデータ列の整列は完了します。したがって(3)の処理が繰り返される回数は2回です。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop