4 ソートのまとめ

コンピューターでは，大量のデータを取り扱う．その場合，データが規則どおりに並んでいることが重要である．規則どおりに並んでいると，データを探す時間を大幅に短縮できる．これは，人間が図書館であるタイトルの本を探すときや，英和辞典で単語を調べるときと同じである．

規則どおりにデータを並べることをソート(sort)³という．ここでは，整数のデータを小さい順(昇順)に並べる方法を学習した．ここでは述べなかったが，逆に大きい順のことを降順と言う．講義では，以下のソートについて学習した．

• バブルソート

  数列の隣どうしの要素の大小を比較してそれらを交換しながらソートする方法である。交換が1回も生じなかったら，ソートが完了である．これは，小さい値のデータが泡(バブル；bubble)のように浮かんで行くように見える⁴ことからこの名前がつけられた。

• クイックソート

  ある一つの要素を基準とし基準値より大きいグループと小さいグループに分ける．分けられたグループも同様の方法で分ける．全てのグループの要素が1つになるまでこの作業を繰りかえし，このときソートが完了する．いろいろなソートの中で，平均的には最速であるから，この名前がついている．

• マージソート

  最初に少ない個数の数列を並べ替えたグループを作る．次に、2つのグループを併合(マージ)して，より大きな並び替えられたグループを作る．これを繰り返すことにより，大きなグループができ，最終的には一つのグループになり並び替えが終了する．

• コームソート

  バブルソートは隣との比較のため，小さい値は一つずつしか移動できない(昇順)．比較する間隔を広くして，一気に移動させる方法がコームソートである．このソートでは，適当な間隔でバブルソートを行い徐々にその間隔を狭める方法がとられる．実験から，間隔は$1/1.3$ ずつ小さくしていくのが良いと言われている．最終的には隣との比較(間隔が1)を行い，交換が起こらなければソートの完了である．

• 単純挿入ソート

  まず，最初の数列の2つを比較して，小さいほうを左に，大きいほうを右にする．次に数列の3番目を，その左にある2つの数列と小さいほうから順に比較し，収まる位置を探索して，挿入する．これを，4番目,5番目，$\cdots$ と順次，数列の最後まで繰り返す．最後の数列が挿入されたらソートが完了である．

• 2分挿入ソート

  単純挿入ソートでは，数列のある値を挿入する適当な位置は端から順に探している(リニアーサーチ)，位置を探す数列は並べ替えられているので，真中の値から比較するバイナリーサーチが可能で，それを適用して速度の向上を図った方法が，2分挿入ソートである．

これら学習したソートの計算量と安定性については，表1(教科書の Table 1-2)のとおりである．

表 1: ソートのアルゴリズムの特徴

アルゴリズム	計算量オーダー	安定性
バブルソート	$O(N^2)$	安定
クイックソート	$O(N\log N)$ 〜$O(N^2)$	不安定
マージソート	$O(N\log N)$	安定
コームソート	$O(N\log N)$	不安定
単純挿入ソート	$O(N^2)$	安定
2分挿入ソート	$O(N^2)$	安定

ホームページ: Yamamoto's laboratory
著者: 山本昌志