サンプル問題1 問42

5個のデータ列を次の手順を繰り返して昇順に整列するとき,整列が完了するまでの手順の繰返し実行回数は幾つか。

〔整列前のデータの並び順〕
 5,1,4,3,2

〔手順〕
  • 1番目のデータ>2番目のデータならば,1番目と2番目のデータを入れ替える。
  • 2番目のデータ>3番目のデータならば,2番目と3番目のデータを入れ替える。
  • 3番目のデータ>4番目のデータならば,3番目と4番目のデータを入れ替える。
  • 4番目のデータ>5番目のデータならば,4番目と5番目のデータを入れ替える。
  • 一度も入替えが発生しなかったときは,整列完了とする。
     入替えが発生していたときは,(1) から繰り返す。

  • 1
  • 2
  • 3
  • 4
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズムとプログラミング
解説
この整列手法は基本交換法(バブルソート)と呼ばれるもので、隣り合う要素を比較し大小関係が逆順になっていればその二つの要素の位置を交換することを繰り返すことで整列を行います。
昇順とは、値の小さい順ということなので、数字が小さい順から「1,2,3,4,5」になるまで〔手順〕を繰り返していきます。(逆に大きい順の場合は降順といいます)
  1. 1回目の手順で、1,4,3,2,5
  2. 2回目の手順で、1,3,2,4,5
  3. 3回目の手順で、1,2,3,4,5
  4. 3回目で入替えが発生しているので4回目の〔手順〕を行います。すでに3回目で昇順に整列済みなので4回目では入れ替えは発生しません。
ということで整列されるまでに繰り返される〔手順〕の回数は4回ということになります。

Pagetop