並べる前に「何を比べるか」を決める

名簿なら氏名の五十音順、商品一覧なら価格の安い順、試合結果なら得点の高い順というように、整列には比較の基準が必要です。この基準に使う値を「キー」と呼びます。同じデータでも、キーと順序を変えれば結果は変わります。小さいものから並べるのが昇順、大きいものから並べるのが降順です。文字列では、文字コードや言語ごとの規則など、どの比較規則を採用するかも結果に関わります。

たとえば、商品番号・商品名・価格を一組にしたレコードを価格順にするとき、比較するキーは価格ですが、入れ替えるのは価格だけではありません。同じ商品に属する商品番号と商品名も一緒に移動させます。プログラムでは、こうしたレコードを配列などに格納し、比較と移動を繰り返します。整列は単なる数字の並べ替えではなく、「どのデータを一単位として、どんな規則で比べるか」を明確にする処理なのです。

交換・選択・挿入で動き方が変わる

基本的な整列方法は、カードを机の上で並べる様子に置き換えると理解しやすくなります。ただし、同じ完成形を目指しても、途中で比べる場所やカードを動かす回数は方法ごとに異なります。

  • バブルソートは、隣り合う二つを比べ、逆順なら交換します。端から順に比較する操作を繰り返すと、大きい値または小さい値が少しずつ端へ移動します。
  • 選択ソートは、未整列の範囲から最小値などを探し、その範囲の先頭と交換します。一回の操作ごとに、正しい位置が一つずつ確定します。
  • 挿入ソートは、整列済みの範囲を少しずつ広げます。次の要素を取り出し、整列済みの範囲内にある適切な位置へ差し込みます。

これらは処理を順番に追いやすく、アルゴリズムの違いを比較する題材になります。一方、入力が大きくなると比較や交換が大幅に増える場合があります。「手順が短く説明できること」と「大きなデータを速く処理できること」は、同じ意味ではありません。

分けてから整えるクイックソートとマージソート

大量のデータを扱う代表的な考え方が、問題を小さく分けて処理する方法です。クイックソートでは、基準となる値を一つ選び、それより小さい側と大きい側にデータを分けます。分けた各部分にも同じ処理を適用して整列します。基準値の選び方や入力の並び方によって分割の偏りが変わるため、常に同じ速さになるわけではありません。

マージソートでは、データを小さな部分に分割し、整列済みの部分どうしを順序よく併合します。併合とは、両方の先頭を比較し、小さいほうから新しい並びへ取り出していく操作です。分割した部分に同じ処理を行う構造は、処理の中から同じ処理を呼び出す再帰で表せます。ただし、実装方法は再帰だけに限られません。

クイックソートとマージソートは、どちらも分割を利用しますが、同じ手順ではありません。クイックソートは分割の過程で要素の位置を整え、マージソートは分割後の併合で順序を作ります。名前だけでなく、データがいつ整列されるのかを追うことが区別のポイントです。

データが増えたときの差を計算量で見る

整列方法の速さは、特定のコンピュータで測った秒数だけでは比較しきれません。入力の個数を n とし、比較や交換などの基本操作がどの程度増えるかを表す計算量を使うと、データ量が増えたときの傾向を比べられます。

単純な整列方法の多くは、最悪の場合に操作回数が n の二乗に比例する形で増えます。これに対し、マージソートは入力を半分ずつに分けて併合するため、比較回数の増え方をおおむね n log n に抑えられます。クイックソートも分割がうまく進む場合はおおむね n log n ですが、分割が極端に偏る場合には n の二乗に比例するまで増えることがあります。

選択では速さ以外も重要です。追加の記憶領域をどれほど使うか、もとの並びがほぼ整列済みか、同じキーを持つ要素が多いかによって適した方法は変わります。そのため、「どんな入力でも一つの整列方法が最良」とは限りません。実際のプログラミング言語やライブラリが提供するソート機能では、利用者が比較規則を指定するだけで使えるものもあります。

ソートの「安定」は壊れにくさの意味ではない

整列アルゴリズムについていう「安定」は、故障しにくい、結果が正確といった日常語の意味ではありません。同じキーを持つ要素どうしの元の順序が、整列後も保たれる性質を「安定」といいます。これは、複数の基準で段階的に並べるときに役立つ、少し意外な専門用語です。

たとえば、商品を先に商品名順に並べ、次に価格だけをキーとして安定な方法で整列するとします。同じ価格の商品どうしでは、先に作った商品名順が残ります。反対に、不安定な方法では同価格の商品の順序が入れ替わる可能性があります。バブルソートや挿入ソートは、同じ値を交換しないように実装すれば安定にできます。一般的な選択ソートは、離れた要素の交換によって同じ値の順序が変わることがあるため、安定ではありません。方法の名前だけで判断せず、実際の比較条件と移動方法を確かめる必要があります。

並べ終えると二分探索への扉が開く

整列そのものが最終目的とは限りません。順位表を作る、中央値を求める、同じ値をまとめる、重複を見つけるなど、次の処理を行いやすくする準備としても使われます。特に、整列済みデータでは、中央の値と目的の値を比べて探索範囲を半分ずつ狭める二分探索が使えます。

一度だけ値を探すなら、整列せず先頭から調べるほうが手間の少ない場合もあります。しかし、同じデータから何度も探すなら、先に整列する費用をかけても、その後の探索を効率化できることがあります。探索アルゴリズムと整列アルゴリズムは別々の手順ですが、前処理と本処理として組み合わせて考えることで、データ処理全体の効率を判断できます。