選択法と挿入法｜基礎を学ぶ

途中経過で3つを見分ける

前回の交換法に続いて、基本的な整列法があと2つあります。選択法と挿入法です。この3つは最終結果が同じなので、試験では「途中経過の並び」を見せて、どの方法かを当てさせる形で出てきます。名前と定義を覚えるだけでは足りず、1回の走査でどこがどう変わるかを言えるようにしておく必要があります。

選択法は最小値を探して先頭へ

選択法は、まだ並んでいない範囲から最小値を探し、その範囲の先頭と交換する方法です。

○整数型の配列: sentakuhou(整数型の配列: data)
 整数型: i, j, min, tmp
 for (i を 1 から dataの要素数 - 1 まで 1 ずつ増やす)
   min ← i
   for (j を i + 1 から dataの要素数 まで 1 ずつ増やす)
     if (data[j] < data[min])
       min ← j
     endif
   endfor
   tmp ← data[i]
   data[i] ← data[min]
   data[min] ← tmp
 endfor
 return data

内側の for では交換をせず、いちばん小さい値がある位置を min に覚えるだけです。走査を1回終えてから、まとめて1回だけ交換します。ここが交換法との大きな違いで、比較回数は同じでも交換回数はずっと少なくなります。

{5, 3, 4, 1, 2} に選択法をかけると、1回目で最小の 1 が先頭に来て {1, 3, 4, 5, 2} になります。前から確定していき、確定していない部分の並びは元のままに近い、というのが選択法の見た目です。

挿入法は手札を並べるように差し込む

挿入法は、トランプの手札を1枚ずつ抜き出して、すでに並べた札の正しい位置へ差し込む動きです。

○整数型の配列: sounyuuhou(整数型の配列: data)
 整数型: i, j, tmp
 for (i を 2 から dataの要素数 まで 1 ずつ増やす)
   tmp ← data[i]
   j ← i - 1
   while (j ≧ 1 and data[j] > tmp)
     data[j + 1] ← data[j]
     j ← j - 1
   endwhile
   data[j + 1] ← tmp
 endfor
 return data

外側の for が 2 から始まるのは、1個だけの部分はすでに並んでいるとみなせるからです。while の中では比較して大きいものを1つ後ろへずらし、空いた場所に tmp を落とします。

{5, 3, 4, 1, 2} に挿入法をかけると、1回目で 3 が 5 の前に入って {3, 5, 4, 1, 2} になります。前のほうだけがきれいに並び、後ろは手つかずのまま、というのが挿入法の見た目です。

見分け方

3つの違いを言葉にすると、交換法は末尾から確定し、選択法は先頭から確定し、値そのものは元の位置に近いまま残ります。挿入法は前半だけが並んでいて後半は完全に元のままです。並びを見せられたら、まず「どこまでが確定しているか」と「未確定部分は元のままか」の2点を見てください。

なお挿入法は、すでにほぼ並んでいるデータに対しては while がほとんど回らず非常に速くなります。データの状態によって速さが変わるアルゴリズムがある、という点も試験で問われます。