逐次ソート

逐次ソート
2011/05/16
ソート(sort)
• 順序集合の要素a1…anの上下関係を整える
• 一般的には、整数の集合Nを考えればよい
• ソートの計算量が問題となる
• どのような入力に対し、どのようなアルゴリ
ズムが最適か?
安定なソート・不安定なソート
• 安定なソート
同じ値の要素が複数あったときにソート後順番が保たれ
ている
4 51 1 52 7
1
4
51
52
7
52
51
7
• 不安定なソート
ソート後の順番が保障されていない
1
4
計算量(1)
• オーダー(order)
O()
• ソートアルゴリズムが、データ個数nに対しど
れだけの計算時間を必要とするかの目安
• 高速なコンピュータでも、アルゴリズムが適切
でないと、nが大きくなったときに破綻する
計算量(2)
(例)ある入力nに対し
アルゴリズムF1の計算時間が
F1(n)=C1 n + C2
アルゴリズムF2の計算時間数が
F2(n)=D1 n2 + D2 n+D3
F1(α) < F2(α)となるようなαが存在する
計算量(3)
• ステップ数の最大項をとる
O(n2+n)= O(n2)
O(log n +n2)=O(log n)
O(nn)>O(n2)>O(n log n)>O(log n)>O(n)
• 最大項の係数は無視してよい
O(kn2+ln)= O(n2)
比較によるアルゴリズム
計算量 O(n2)
• バブルソート(bubble sort)
• 挿入ソート(insert sort)
計算量 O(n log n)
• クイックソート(quick sort)
• ヒープソート(heap sort)
• マージソート(marge sort)
比較によらないアルゴリズム
計算量 O(n)
ただし制限あり
• バケットソート(backet sort)
大量のメモリを必要とする
• 基数ソート(radix sort)
バケットソートよりも遅い
アルゴリズムによる計算時間
いろいろな計算量
• 最速計算量
当然
O(n)
• 最悪計算量
もっとも悪いパターンのときの計算量
O(n log (n)) が上界
• 平均計算量
n!のパターンの平均計算量
決定木(比較木)(1)
計算量の抽象化
決定木(比較木)
• アルゴリズムの動きを概念化
• 二分探索木と似ているが、違う概念であることに注意
決定木(比較木)(2)
決定木(比較木)(3)
決定木の平均深さはlog2 n! 以上
計算量の上界
O(log2 n!) = O(log n*n) =O (n log n)
• n校によるトーナメント試合の試合数
決定木(比較木)(4)
• 二分探索木の平衡木・AVL木について
の議論は適用できる
• 平衡木を作ることがそのまま計算量の
上界を求めることになる
• もっとも深い葉が最悪計算量に相当す
る
ベンチマークテスト
参考文献
• http://www.ics.kagoshimau.ac.jp/~fuchida/edu/algorithm/sort-algorithm/
• The Art of Computer Programming Vol.Ⅲ
D.A.Knuth ASCII出版
バイブル。大著であるが親切に書かれており初学者にも
意外とわかりやすい
理論面を丁寧に記述している
練習問題が豊富 (だが5分で解ける問題、とかうざい設
定がしてある)
• 定本Cプログラミングのためのアルゴリズムとデータ構造
近藤嘉雪 SOFTBANK BOOKS
簡潔で実用的。理論的な面は追及していない
順序集合
• 集合の要素間に上下関係を与えたもの
ある集合Aの任意2つの要素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の2つの要素a, b に対し、a ≤ b ま
たは b ≤ a のいずれか、あるいは両方が成り立
つとき、a と b は比較可能(comparable) であると
いいう
• 順序集合 (A, ≤) の任意の2つの要素a, bが比較
可能であるとき、順序 ≤ は全順序 (total order) ま
たは線型順序 (linear order) であるといい、順序
集合 A は全順序集合 (totally ordered set) である
という(完全律 (totalness))
順序集合の例
• 整数の部分集合A⊆Zは算術演算に対し順序集
合、かつ全順序集合
(ただし、複素数Cは順序集合ではない)
• グー、チョキ、パーは感覚的勝敗に対し順序集
合ではない
(推移則が成り立たない)
• 集合A⊂N={4,1,4,7,8}
は普通の算術演算に対し順序集合
(要素4が2つあるので、前順序集合)