アルゴリズムとデータ構造

アルゴリズムと
データ構造
第10回
ソート・その4
ヒープソート

ヒープソートとは
 ヒープを用いて行うソート

ヒープ

どの親も必ず子より大きい値となっている完全2分木
9
7
5
8
4
6
ヒープソート

配列によるヒープの表現
 a[i]の親はa[(i
- 1) / 2]
 a[i]の左の子はa[i * 2 + 1]
 a[i]の右の子はa[i * 2 + 2]
a[0]
a[1]
a[3]
a[7]
a[2]
a[4]
a[8]
a[5]
a[6]
ヒープソート

配列によるヒープの表現
10
9
5
8
6
3
7
10
9
2
4
1
5
8
3
2
4
6
7
1
ヒープソート

ヒープソートの考え方
 ヒープの根から値を取り出す：最大値が得られる
 取り出した値を後ろから並べる：昇順ソート完了
 取り出された値は削除→ヒープが崩れる：木が再
びヒープになるよう再構築
ヒープソート

根の削除と再構築
 根を削除後、ヒープの最後の要素を根に移動
移動した根以外はヒープ状態を維持
 移動した最後の要素を適切な位置に移動すれば全体
が再びヒープ状態になる

 2つの子と比較、大きい方の子と交換
ただしどちらの子よりも大きかったらそこで終了
 葉まで到達した時点でも終了

ヒープソート

根の削除と再構築
10
9
8
9
5
8
7
6
3
7
1
1
2
4
ヒープソート

ヒープソートへの拡張
10
9
8
9
5
8
7
6
3
7
1
10
9
9
8
2
4
1
5
8
7
3
2
4
6
7
1
10
1
ヒープソート

ヒープソートへの拡張
9
8
8
7
5
7
6
6
1
3
2
4
1
9
8
8
7
5
7
6
3
2
4
6
1
1
9
10
ヒープソート

ヒープソートへの拡張
8
7
7
6
5
6
1
3
2
4
1
8
7
7
6
5
6
1
3
2
4
1
8
9
10
ヒープソート

ヒープソートへの拡張
7
6
6
4
5
1
7
6
3
6
4
5
2
1
3
2
4
4
7
8
9
10
ヒープソート

ヒープソートへの拡張
6
5
4
2
5
1
6
5
3
4
5
2
2
1
3
2
6
7
8
9
10
ヒープソート

ヒープソートへの拡張
4
5
4
3
2
1
5
4
3
4
3
2
1
3
5
6
7
8
9
10
ヒープソート

ヒープソートへの拡張
4
3
3
1
2
1
4
3
1
3
2
1
4
5
6
7
8
9
10
ヒープソート

ヒープソートへの拡張
3
1
2
1
2
3
1
1
2
2
2
3
4
5
6
7
8
9
10
ヒープソート

配列のヒープ化
 ある親の左右の部分木が両方ともヒープになって
いれば、その親を適当な位置まで下ろすとヒープ
 下流側の小さい部分木から順に、ボトムアップ的
に積み上げれば、全体もヒープ
ヒープソート

配列のヒープ化
10
1
10
9
3
5
8
7
6
10
3
9
7
8
10
9
3
1
2
4
度数ソート

度数ソートとは
 別名：分布数えソート
 比較を行う必要がないソート
 データの最小値と最大値がわかっている場合の
み適用可能
 非常に高速
 安定したソート
度数ソート

度数ソートの手順
 Step1：度数分布表の作成

各値を持つ要素の個数を表す度数分布表を作成
 Step2：累積度数分布表の作成

最小値からある値までの要素数を表す累積度数分布
表を作成
 Step3：目的配列の作成

原配列の各要素値と累積度数分布表から、ソート済
み配列を作成
度数ソート

度数ソートの手順
 Step1：度数分布表の作成
a
5
7
0
2
4
10
3
1
3
f
0
1
0
1
1
0
2
1
0
3
1
0
2
4
1
0
5
1
0
6
0
7
1
0
8
0
9
0
10
1
0
度数ソート

度数ソートの手順
 Step2：累積度数分布表の作成
f
0
1
1
1
2
1
3
2
4
1
5
1
6
0
7
1
8
0
9
0
10
1
f
1
2
3
5
6
7
7
8
8
8
9
度数ソート

度数ソートの手順
 Step3：目的配列の作成
a
5
7
0
2
4
10
3
1
3
0
1
2
3
4
5
6
7
8
9
10
f
0
1
1
2
2
3
3
4
5
5
6
6
7
7
7
8
8
8
8
9
b
0
0
1
1
1
2
2
2
3
3
3
4
4
3
5
5
4
6
6
5
7
7
7
8
8
10
9

Download Report