整列アルゴリズム

整列（ソート）とは、データの集まりを指定したキーの大小に従って並べ替える処理である。整列アルゴリズムは、隣接する要素の交換、基準値による分割、挿入、最小値の選択など基本となる操作が異なり、それぞれ計算量や安定性などの性質が異なる。試験では、途中の状態からアルゴリズムを特定する問題と、手順の回数や分割の結果を求める問題が中心になる。

隣接要素の交換を繰り返すバブルソート

バブルソートは、隣接する二つの要素の大小を比べ、順序が逆であれば入れ替える操作を繰り返す方法である。配列を左から走査すると、各走査で未整列部分の最大値が右端へ移動するため、走査を重ねるごとに整列済み部分が右から広がる。途中経過の並びを見て、最大値が1回の走査で末尾へ移るような推移が読み取れれば、バブルソートであると判断できる。

バブルソートは隣接要素の比較と交換だけで整列を進めるため、基準値を用いるクイックソートや、一定間隔で部分列を作るシェルソートとは操作の単位が異なる。

また、順序が逆の場合にだけ交換を行うため、同じ値の要素は入れ替わらない。この点から、バブルソートは安定な整列法とされる。

基準値による分割を行うクイックソート

クイックソートは、基準値（ピボット）を一つ選び、それより小さい値のグループと大きい値のグループに分け、各グループを再帰的に同じ方法で整列する方法である。分割後は基準値が両グループの境界に位置するため、分割の結果を左から順に追えば途中経過が決まる。基準値の選び方によって分割が偏ると処理が遅くなるため、その影響を考慮する必要がある。

問題の条件として、グループ内の要素の並び順を元の配列と同じに保つ場合は、分割のたびに基準値の右側に残るグループを対象とすることが手順になる。1回目の分割で整列されたのは基準値の左右の区分であり、2回目の分割は右側のグループを対象とする。

間隔を縮めながら挿入法を行うシェルソート

シェルソートは、一定の間隔 H で離れた要素の集まりを部分列とし、それぞれを挿入法で整列する操作を、間隔を縮めながら繰り返す方法である。間隔は H ← ⌊H÷3⌋ のように更新され、H が0になった時点で整列が完了する。データ数が9の場合、初期の間隔は3になり、その後に1、そして0へと変化するので、間隔を更新する手順は2回繰り返される。