整列アルゴリズムの仕組み

整列とは、データ列を指定したキーの大小順に並べ替える処理であり、整列アルゴリズムは比較・交換・分割・挿入などの操作を組み合わせてそれを実現する方法である。代表的な方法は、隣接要素の交換を繰り返すもの、基準値で分割するもの、一定間隔の部分列を整列して間隔を縮めるもの、順序木を利用するものに分けられる。方法ごとに途中の並びの変化が異なるため、途中の状態から方法を特定する問いが多く出題される。

隣接要素の交換によるバブルソート

バブルソートは、隣り合う要素を比較し、順序が逆であればそれらを入れ替える操作を繰り返す方法である。配列全体を何度も走査し、交換がなくなった時点で整列が完了する。

1回の走査では、未整列部分の最大値が右端へ運ばれて確定する。このため途中の状態は、末尾から大きい値が順に並んでいく形で現れる。最初の走査で最大の値が末尾へ移り、次の走査で次に大きい値が末尾から二番目へ移るという推移が、バブルソートの典型である。

基準値による分割のクイックソート

クイックソートは、基準値より小さい値と大きい値のグループに分け、各グループに同じ処理を再帰的に適用する方法である。基準値の選び方と、グループ内の並びを元の順序のまま保つかどうかによって、途中の並びは大きく変わる。

例えば、左端の値を基準値とする分割では、基準値より小さい値はすべて基準値の左側へ移る。一方、分割する部分列の中に基準値より小さい値がなければ、その部分列の並びは元のまま残る。2回目の分割の結果を求める場合は、1回目の分割で作られたグループの区切りを正しく把握してから次の分割を適用する必要がある。

間隔の縮小を繰り返すシェルソート

シェルソートは、一定の間隔 H だけ離れた要素からなる部分列を挿入法で整列し、H を小さくしながら同じ処理を繰り返す方法である。最後は間隔1で全体を整列する点が特徴である。