逐次ソート 2011/05/16

ソート（ｓｏｒｔ） 順序集合の要素ａ １ … ａ n の上下関係を整 える 一般的には、整数の集合 N を考えればよ い ソートの計算量が問題となる どのような入力に対し、どのようなアル ゴリズムが最適か？

安定なソート・不安定なソート 安定なソート 同じ値の要素が複数あったときにソート後順番が保 たれている ４ ５ １ １ ５ ２ ７ １ ４ ５ １ ５ ２ ７ 不安定なソート ソート後の順番が保障されていない １ ４ ５ ２ ５ １ ７

計算量（１） オーダー（ order) O （） ソートアルゴリズムが、データ個数ｎに 対しどれだけの計算時間を必要とするか の目安 高速なコンピュータでも、アルゴリズム が適切でないと、ｎが大きくなったとき に破綻する

計算量（２） （例）ある入力ｎに対し アルゴリズム F 1 の計算時間が F １ （ｎ）＝ C １ ｎ ＋ C ２ アル ゴリズム F 2 の計算時間数が F 2 （ｎ）＝ D １ ｎ ２ ＋ D ２ ｎ＋ D ３ Ｆ 1 (α) ＜ Ｆ 2 (α) となるような α が存在する

計算量（３） ステップ数の最大項をとる Ｏ（ｎ ２ ＋ｎ）＝ Ｏ（ｎ ２ ） Ｏ（ｌｏｇ ｎ ＋ｎ ２ ）＝Ｏ（ｌ ｏｇ ｎ） O(n n )>O(n 2 )>O(n log n)>O(log n)>O(n) 最大項の係数は無視してよい Ｏ（ｋｎ ２ ＋ｌｎ）＝ Ｏ（ｎ ２ ）

比較によるアルゴリズム 計算量 O(n 2 ) バブルソート（ bubble sort) 挿入ソート (insert sort) 計算量 O(n ｌ o ｇ n ） クイックソート (quick sort) ヒープソート (heap sort) マージソート (marge sort)

比較によらないアルゴリズム 計算量 O(n) ただし制限あり バケットソート（ backet sort) 大量のメモリを必要とする 基数ソート (radix sort) バケットソートよりも遅い

アルゴリズムによる計算時間

いろいろな計算量 最速計算量 当然 O(n) 最悪計算量 もっとも悪いパターンのときの計算量 Ｏ（ n log (n) ） が上界 平均計算量 ｎ！のパターンの平均計算量

決定木（比較木）（１） 計算量の抽象化 決定木（比較木） アルゴリズムの動きを概念化 二分探索木と似ているが、違う概念であることに注 意

決定木（比較木）（２）

決定木（比較木）（３） 決定木の平均深さは log 2 n! 以上 計算量の上界 Ｏ（ log2 n! ） = Ｏ（ log n*n) =O (n log n) ｎ校によるトーナメント試合の試合数

決定木（比較木）（４） 二分探索木の平衡木・ＡＶＬ木につ いての議論は適用できる 平衡木を作ることがそのまま計算量 の上界を求めることになる もっとも深い葉が最悪計算量に相当 する

ベンチマークテスト

参考文献 u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/ u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/ The Art of Computer Programming Vol. Ⅲ D.A.Knuth ASCII 出版 バイブル。大著であるが親切に書かれており初学者 にも意外とわかりやすい 理論面を丁寧に記述している 練習問題が豊富 （だが５分で解ける問題、とかう ざい設定がしてある） 定本 C プログラミングのためのアルゴリズムとデータ 構造 近藤嘉雪 SOFTBANK BOOKS 簡潔で実用的。理論的な面は追及していない

順序集合 集合の要素間に上下関係を与えたもの ある集合 A の任意２つの要素 a 、 b に与えら れた二項関係により、 前順序集合 半順序集合 全順序集合 などが定義される

前順序集合 集合 A のすべての要素 a 、 b に対し二項関 係 (A,≤ ) があって、 反射則 : a ≤ a 推移則 : a ≤ b かつ b ≤ c ならば a ≤ c が成り立つとき、これを半順序集合という

半順序集合 集合 A のすべての要素 a 、 b に対し二項関 係 (A,≤ ) があって、 反射則 : a ≤ a 推移則 : a ≤ b かつ b ≤ c ならば a ≤ c 反対称律 : a ≤ b かつ b ≤ a ならば a = b が成り立つとき、これを半順序集合という

全順序集合 半順序集合 A の２つの要素 a, b に対し、 a ≤ b または b ≤ a のいずれか、あるいは両方 が成り立つとき、 a と b は比較可能 (comparable) であるといいう 順序集合 (A, ≤) の任意の２つの要素 a, b が比較 可能であるとき、順序 ≤ は全順序 (total order) または線型順序 (linear order) であると いい、順序集合 A は全順序集合 (totally ordered set) であるという（完全律 (totalness) ）

順序集合の例 整数の部分集合 A ⊆ Z は算術演算に対し順序集 合、かつ全順序集合 （ただし、複素数 C は順序集合ではない） グー、チョキ、パーは感覚的勝敗に対し順序 集合ではない （推移則が成り立たない） 集合 A ⊂ N={ ４，１，４，７，８｝ は普通の算術演算に対し順序集合 （要素４が２つあるので、前順序集合）