配列に格納されたデータ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
(ア)のままである。
【キーワード】
・整列方法
- 整列方法(ソート)
データの並び替えのことで様々な方法がある。- クイックソート
ソートするデータから、適当な数を選択し、データをその数より大きいほうと小さいほうに分け、分けたデータに対し、この操作を繰り返す。 - シェルソート
適当に間隔を開けたデータを取り出し並び替えを行い、間隔を小さくしながらこの操作を繰り返す。 - バブルソート
n個のデータに対して、データの1番目と2番目を比較し順番が逆なら入れ替え、次に2番目と3番目で比較し、…、n-1番目とn番目で比較を行う。(n番目のデータの整列)
その次に、1番目と2番目、2番目と3番目、…、n-2番目とn-1番目。(n-1番目のデータの整列)
その次に、1番目と2番目、2番目と3番目、…、n-3番目とn-2番目。(n-2番目のデータの整列)
この処理を繰り返し行い整列する。 - ヒープソート
未整列のデータから要素を1個づつ取り出し、ヒープ構造を作りながらデータのソートを行う。 - マージソート
データ列を2分割し、2分割したデータ列に対しソートを行い、分割したデータ列を合わせて(マージして)ソートを行う。
- クイックソート
もっと、「クイックソート」について調べてみよう。
戻る
一覧へ
次へ