次のうち、「不安定な整列 (ソート) アルゴリズム」として最も適切なものはどれか。ここで不安定とは等しい要素同士の出現順序を保つ保証がないことをいう。
① 基数ソート ② 計数ソート ③ 選択ソート
④ 挿入ソート ⑤ マージソート
③
不安定ソートは、例えば会員番号順に並んでいる顧客
01:300円
02:400円
03:300円
04:100円
を、顧客の商品購入額の低い順にソートするような場合、
04:100円
03:300円
01:300円
02:400円
のように同じ金額の場合に、ソート前の順序を保つ保証がないソート方法である。
安定したソートの場合、
04:100円
01:300円
03:300円
02:400円
のように、同じ金額の場合に、ソート前の順序を保つことを保証できる。
① 基数ソートは、一の位など下位の桁から順にソートしていき、最後に最上位の桁でソートして、全体として整列する手法である。
安定ソートである。
② 計数ソートは、データの取り得る全ての容器を順番通りに並べて置き、値を対象の容器に移し、その後、容器から順に値を取り出して整列する手法である。データが取り得る値が判らない時はこのソート方法は使えない。バケツソートとも呼ばれる。
安定ソートである。
③ 正しい。選択ソートは、データの中から最小値 (最大値) を探し、配列の左端からと交換しながら、整列する手法である。上記の例では、まず、会員番号01と04が入れ替わり、
04:100円
02:400円
03:300円
01:300円
次に、会員番号02と03が入れ替わり、
04:100円
03:300円
02:400円
01:300円
最後に、会員番号02と01が入れ替わる。
04:100円
03:300円
01:300円
02:400円
結果、会員番号03と01の順序が保てなくなっている。
④ 挿入ソートは、最初の2つの要素を比較して、整列し3番目以降は、整列された範囲の中の適切な位置に挿入していく手法である。
安定ソートである。
⑤ マージソートは、隣り合う配列ごとにソートとマージ (併合) を繰り返すソート方法である。例えば、61734825は、以下の順に整列される。
16 37 48 25 ⇒
1367 2458 ⇒
12345678
安定ソートである。
| Ⅰ－１ | 目次 | Ⅰ－３ |