レポートの答え 内部ソート/外部ソート その場整列 余分なメモ リ

2016/11/17
レポートの答え
データ構造とアルゴリズム
（第６回）
ーデータの整列ー
選択／挿入による方法
void graph_search(start)
int start;
{
int n,j,k;
stack S;
Init(S);
Add(S,start);
Visit[start]=YES;
while(Not_Empty(S)){
n=Get_And_Delete(S);
for(j=0;j<4;j++){
if(AdjMatrix[n][j]==1){
if(Visit[j]==NO){
Add(S,j);
Visit[j]=YES;
}}}}
データの整列
•
安定なソート
全順序が定義されている集合の部分集合が与
えられたとき、この順序にしたがって、各要素を
並べ替える操作。
降順（高さに関して)
年齢順
収入順（安定ではない）
収入順（安定）
30
800
1
田中
田辺
40
30
800
1
佐々木 40
950
5
田辺
田中
30
40
800
1
田中
40
800
1
佐々木 40
950
5
山田
49
1050
4
山田
1050
4
田辺
49
昇順（高さに関して)
内部ソート/外部ソート
CPU＆MEMORY
DISK
その場整列
8
8
8
8
4
4
7
7
6
7
4
6
7
6
6
4
2
2
2
2
1
1
1
1
余分なメモ
リ領域を必
要としない
ソート
1
2016/11/17
ソートアルゴリズムの分類
単純選択法のアルゴリズム
•キーの比較に基づく方法
n 選択（n番目に来るキーを選択する）
n 挿入（キーを入れる場所を見つけ、挿入する）
n 交換（キー同士を交換する）
n 併合(整列された短い並びを併合していく）
•キーの構造に基づく方法
n 交換（キー同士を交換する）
n 分散（キーを分散させながら整列する）
単純選択法
ヒープソート：ヒープとは？
任意の節に格納されるキー
の値がその子の節に格納
されるキーの値以上である
ような完全二分木
ヒープの作り方
Shiftによるヒープの作り方
部分木がすでにヒープに
なっている段階から考える.
ヒープの上に
あるノードが付
け加わると…
heap
heap
2
2016/11/17
Shiftの手続き
ヒープソートの基本的考え方
完全二分木の第r要素
以降、s番目までをheap
にする。
r
2*r
s
ヒープの根は最大値なので、それを最後尾にまわせばよい。
r
r’
r’’
r
r’ r
ヒープソートのアルゴリズム
ヒープソートの計算過程
選択による方法：まとめ
ソートアルゴリズムの分類
•単純選択法：
安定ではない、キー比較回数O(n )、
キー移動回数n-1
•ヒープソート法:
安定ではない、計算のオーダ
O(n log(n))、ヒープの形が徐々
に変化するので、迅速に最大の
キーが選択できる。
2
•キーの比較に基づく方法
n 選択（n番目に来るキーを選択する）
n 挿入（キーを入れる場所を見つけ、挿入する）
n 交換（キー同士を交換する）
n 併合(整列された短い並びを併合していく）
•キーの構造に基づく方法
n 交換（キー同士を交換する）
n 分散（キーを分散させながら整列する）
3
2016/11/17
単純挿入法のアルゴリズム
単純挿入法の実行例
シェル法の実行例
シェル法のアルゴリズム
挿入による方法：まとめ
•単純挿入法：
安定、キー比較回数O(n )、
キー移動回数O(n )
•シェル法:
安定ではない、計算のオーダ
は解析的に議論しにくい、概整列
の効果が大きい。
2
2
4