次のうち、「不安定な整列 (ソート) アルゴリズム」として最も適切なものは
どれか。ここで不安定とは等しい要素同士の出現順序を保つ保証がない
ことをいう。
① 基数ソート ② 計数ソート ③ 選択ソート
④ 挿入ソート ⑤ マージソート
不安定ソートは、例えば会員番号順に並んでいる顧客
０１：３００円
０２：４００円
０３：３００円
０４：１００円
を、顧客の商品購入額の低い順にソートするような場合、
０４：１００円
０３：３００円
０１：３００円
０２：４００円
のように同じ金額の場合に、ソート前の
順序を保つ保証がないソート方法である。
安定したソートの場合、
０４：１００円
０１：３００円
０３：３００円
０２：４００円
のように、同じ金額の場合に、ソート前の順序を保つことを保証できる。
① 基数ソートは、一の位など下位の桁から順にソートしていき、最後に最上位の桁で
ソートして、全体として整列する手法である。
安定ソートである・
② 計数ソートは、データの取り得る全ての容器を順番通りに並べて置き、
値を対象の容器に移し、その後、容器から順に値を取り出して整列する手法である。
データが取り得る値が判らない時はこのソート方法は使えない。バケツソートとも呼ばれる。
安定ソートである。
③ 正しい。選択ソートは、データの中から最小値（最大値）を探し、配列の左端からと
交換しながら、整列する手法である。
上記の例では、まず、会員番号０１と０４が入れ替わり、
０４：１００円
０２：４００円
０３：３００円
０１：３００円
次に、会員番号０２と０３が入れ替わり、
０４：１００円
０３：３００円
０２：４００円
０１：３００円
最後に、会員番号０２と０１が入れ替わる。
０４：１００円
０３：３００円
０１：３００円
０２：４００円
結果、会員番号０３と０１の順序が保てなくなっている。
④ 挿入ソートは、最初の２つの要素を比較して、整列し
３番目以降は、整列された範囲の中の適切な位置に挿入していく手法である。
安定ソートである。
⑤ マージソートは、隣り合う配列ごとにソートとマージ (併合) を
繰り返すソート方法である。
例えば、６１７３４８２５は、以下の順に整列される。
１６ ３７ ４８ ２５ ⇒
１３６７ ２４５８ ⇒
１２３４５７６８
安定ソートである。
EXCEL ＶＢＡのご相談なら ファーストマクロ へ
タグ：ソート
