アルゴリズム(全97問中3問目)

配列に格納されたデータ2,3,5,4,1に対して,クイックソートを用いて昇順に並べ替える。2回目の分割が終わった状態はどれか。ここで,分割は基準値より小さい値と大きい値のグループに分けるものとする。また,分割のたびに基準値はグループ内の配列の左端の値とし,グループ内の配列の値の順番は元の配列と同じとする。

出典:令和5年春期 問 7

  • 1,2,3,5,4
  • 1,2,5,4,3
  • 2,3,1,4,5
  • 2,3,4,5,1
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
クイックソートは、整列対象のデータ群をある基準値以下のグループと基準値以上のグループに分割し、さらに分割後の各グループで基準値を選んで二つのグループに分割するという処理を繰り返してデータを整列するアルゴリズムです。下図のように全体を小集団に分けながら整列を行うので、分割統治型の整列アルゴリズムと言えます。
07.gif
①配列の左端の値を基準値とする、②分割は基準値よりも小さい値と大きい値に分ける、という条件に従って分割を進めていくと次のようなります。
  1. [2,3,5,4,1]
  2. 左端の2より小さいグループ、大きいグループに分ける(1回目の分割)
    [1],[2],[3,5,4]
  3. 各グループで左端の値を基準に小さいグループ、大きいグループに分ける(2回目の分割)
    [1],[2],[3],[5,4]
したがって、2回目分割後の配列の状態は「1,2,3,5,4」です。

Pagetop