配列に格納されたデータ2, 3, 5, 4, 1に対して、クイックソートを用いて昇順に並び替える。 2回目の分割が終わった状態はどれか。 ここで、部活は基準値より小さい値と大きい値のグループに分けるものとする。 また、分割のたびに基準値はグループ内の配列の左端の値とし、グループ内の配列の値の順番は元の配列と同じとする。
ア | 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と3, 5, 4
なので配列は1, 2, 3, 5, 4になる。
左側のグループは要素の数が1個で整列済みなので、右側のグループ3, 5, 4に対して処理を行うと、左端の3を基準として基準値より小さい値と、大きい値に分割するが、全て基準値より大きいので、入れ替えは行われず配列は
1, 2, 3, 5, 4
(ア)のままである。
【キーワード】
・整列方法