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