ソフトウェア開発技術者平成16年春期 午前問11

午前問11

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

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

分類

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

正解

解説

9つの要素を手順に沿って整列していくと、次のようになります。
  1. 9÷3 → H //H=3
  2. Hが3なので、要素ごとが互いに3つずつ離れた要素から成る3つの部分列に分解し、それぞれを整列する。
    11.gif/image-size:325×150
  3. 3÷3 → H //H=1、(3)の処理1回目
  4. Hが0ではないので、(2)の処理に戻る
  5. Hが1なので、要素ごとが互いに1つずつ離れた要素から成る 3,1,6,4,2,8,7,5,9 を整列し、1,2,3,4,5,6,7,8,9 とする。
  6. 1÷3 → H //H=0、(3)の処理2回目
  7. Hが0なので、データ列の整列が完了
したがって完了までに(3)の処理が繰り返される回数は2回です。
© 2010-2022 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop