2015. 5.27
Ibaraki Univ. Dept of Electrical & Electronic Eng.
Keiichi MIYAJIMA
ソーティング2
マージソート
9
8
3
5
7
12
•マージ(merge)とは結合を意味し、分割した列を結合しながら、
ソートを行う。
マージソート
9
8
3
5
•「半分に分割」を再帰的に繰り返す。
7
12
マージソート
9
8
3
5
•「半分に分割」を再帰的に繰り返す。
7
12
マージソート
9
8
3
•「半分に分割」を再帰的に繰り返す。
5
7
12
マージソート
9
8
3
•「半分に分割」を再帰的に繰り返す。
5
7
12
マージソート
9
8
3
5
7
12
•完全にバラバラになった後、隣同士を比較しながら「結合」し
ていく。
マージソート
8 9
3 5
7 12
•完全にバラバラになった後、隣同士を比較しながら「結合」し
ていく。
マージソート
8 9
5
7 12
3
•完全にバラバラになった後、隣同士を比較しながら「結合」し
ていく。
マージソート
8 9
7 12
3 5
•完全にバラバラになった後、隣同士を比較しながら「結合」し
ていく。
マージソート
7 12
9
3 5 8
•完全にバラバラになった後、隣同士を比較しながら「結合」し
ていく。
マージソート
7 12
3
5 8 9
•完全にバラバラになった後、隣同士を比較しながら「結合」し
ていく。
マージソート
7 12
3
5 8 9
•完全にバラバラになった後、隣同士を比較しながら「結合」し
ていく。
マージソート
5 8 9
7 12
3
•完全にバラバラになった後、隣同士を比較しながら「結合」し
ていく。
マージソート
8 9
3
7 12
5
•完全にバラバラになった後、隣同士を比較しながら「結合」し
ていく。
マージソート
8 9
3
5
12
7
•完全にバラバラになった後、隣同士を比較しながら「結合」し
ていく。
マージソート
9
3
12
5 7 8
•完全にバラバラになった後、隣同士を比較しながら「結合」し
ていく。
マージソート
12
3
5 7 8
9
•完全にバラバラになった後、隣同士を比較しながら「結合」し
ていく。
マージソート
3
5 7 8
•残ったものは最後に並べる。
9 12
マージソート
3
5 7 8
9 12
•このような方法を分割統治法ともいう。
•計算量は
O ( n log n )
クイックソート
3
8
9
5
7
12
•系列の先頭の要素を基準とした分割を繰り返す。
クイックソート
3
8
9
5
7
12
•この場合、3を基準に3より大きいものを一番後ろに持って行
く。
クイックソート
3
8
9
5
7
12
•次に、8を基準に8より大きいものを一番後ろに持って行く。
クイックソート
3
5
7
8
9
12
クイックソート
3
5
7
8
9
12
クイックソート
3
5
7
•全てバラバラになったら終了。
8
9
12
クイックソート
3
5
7
8
9
•最悪計算量は O ( n 2 ) だが、平均計算量は
12
O ( n log n )
本日のまとめ
TCP/IPアプリケーション
• ソーティング2
マージソート
クイックソート
本日の課題
• TCP/IPアプリケーション
ランダムに並んだ50万(500,000)個の整数の
データを作成し、以下の5種類のソーティングプロ
グラムでソートを行え。
さらに、実際にソートにかかった時間を比較せよ。
•選択法
•挿入法
•バブルソート
•マージソート
•クイックソート
レポートの〆切と提出先
レポート提出先:
E2棟(旧システム棟)6F606室(宮島教員室)前
レポートBOX
レポート〆切:
6月2日火曜日 PM5:00頃
ダウンロード

ソーティング2(PPTファイル)