第2回 ソート 情報科学科 井口幸洋 [email protected] 2003/5/6 ソフトウェア実習I 1 目的 – データを並べ替える（ソート）技法を学ぶ – ソートは極めて基本的で重要なアルゴリズム – アルゴリズムによって処理速度が大幅に変わるこ との体験をしてもらう 2003/5/6 ソフトウェア実習I 2 ソート方法のいろいろ • バブルソート：1年生の時、学んだ方法． メリットはほとんど無い．プロは使用しない． • 単純挿入法 本日はこの３つの方法を • ヒープソート 実装し，比較を行う． • クイックソート 2003/5/6 ソフトウェア実習I 3 ソート方法のいろいろ • バブルソート：1年生の時、学んだ方法． メリットはほとんど無い．プロは使用しない． • 単純挿入法 • ヒープソート • クイックソート 2003/5/6 ソフトウェア実習I 4 単純挿入法 • 順序正しく並んだ列に新たなデータを正しい 位置に挿入 • n個のデータに対して計算量はO(n2). 2003/5/6 ソフトウェア実習I 5 単純挿入法のアルゴリズム • a[1]～a[i-1]まで既に小さい順（昇順）に整列 されているとする． • 挿入すべき値 q = a[i] とする． • qをa[i-1]からa[1]の方向に向かって挿入すべ き場所を探す．このとき，調べた値がqより大 きければ右に1個づつずらし，q以下になった らそこに挿入して探索を抜け出る． 2003/5/6 ソフトウェア実習I 6 単純挿入法でのソートの例（1） [1][2][3][4][5][6] 2 1 3 5 7 4 まず，a[1]までが整列されて いると考える． [1][2][3][4][5][6] 2 1 3 5 7 4 int i, j, q; for (i = 2; i <= n; i++){ q = a[i]; j = i; while(a[j-1] > q){ a[j] = a[j-1]; j--; } a[j] = q; } a[2]までを整列させる． q=a[2]の内容をどこに挿入すれば 良いか考える． a[1] > qなのでこれを1個右にずらし，そこに挿入! 2003/5/6 ソフトウェア実習I 7 単純挿入法でのソートの例（2） [1][2][3][4][5][6] 1 2 3 5 7 4 a[2]までが整列されている． [1][2][3][4][5][6] 1 2 3 5 7 4 int i, j, q; for (i = 2; i <= n; i++){ q = a[i]; j = i; while(a[j-1] > q){ a[j] = a[j-1]; j--; } a[j] = q; } a[3]までを整列させる． q=a[3]の内容をどこに挿入すれば良いか考える． a[2] < qなので今回は a[3] = q(つまり3)が挿入され， 見かけ上変化はない． 2003/5/6 ソフトウェア実習I 8 単純挿入法でのソートの例（3） [1][2][3][4][5][6] 1 2 3 5 7 4 a[3]までが整列されている． [1][2][3][4][5][6] 1 2 3 5 7 4 int i, j, q; for (i = 2; i <= n; i++){ q = a[i]; j = i; while(a[j-1] > q){ a[j] = a[j-1]; j--; } a[j] = q; } a[4]までを整列させる． q=a[4]の内容をどこに挿入すれば良いか考える． a[3] < qなので今回も a[4] = q(つまり5)が挿入され， 見かけ上変化はない． 2003/5/6 ソフトウェア実習I 9 単純挿入法でのソートの例（4） [1][2][3][4][5][6] 1 2 3 5 7 4 a[4]までが整列されている． [1][2][3][4][5][6] 1 2 3 5 7 4 int i, j, q; for (i = 2; i <= n; i++){ q = a[i]; j = i; while(a[j-1] > q){ a[j] = a[j-1]; j--; } a[j] = q; } a[5]までを整列させる． q=a[5]の内容をどこに挿入すれば良いか考える． a[4] < qなので今回も a[5] = q(つまり6)が挿入され， 見かけ上変化はない． 2003/5/6 ソフトウェア実習I 10 単純挿入法でのソートの例（5） [1][2][3][4][5][6] 1 2 3 5 7 4 a[5]までが整列されている． [1][2][3][4][5][6] 1 2 3 5 7 4 int i, j, q; for (i = 2; i <= n; i++){ q = a[i]; j = i; while(a[j-1] > q){ a[j] = a[j-1]; j--; } a[j] = q; } a[6]までを整列させる． q=a[6]の内容をどこに挿入すれば良いか考える． a[5]から順に大小関係を比較し，ｑの方が小さければ データを右にずらしつつ、挿入位置をさぐる． どのように動作するか検討してみてください． 2003/5/6 ソフトウェア実習I 11 単純挿入法の効率 • 計算の手数：O(n2) • ほぼ整列しているデータ列に対しては効率 が高い． • 効率を探ってみるときのヒント – 小さい順にほぼ並んでいるデータ列 – 大きい順にほぼ並んでいるデータ列 – ランダムに並んでいるデータ列 2003/5/6 ソフトウェア実習I 12 ソート方法のいろいろ • バブルソート：1年生の時、学んだ方法． メリットはほとんど無い．プロは使用しない． • 単純挿入法 • ヒープソート • クイックソート 2003/5/6 ソフトウェア実習I 13 ヒープソート（heap sort） • heap（整列二分木）を使用． • 計算の手数は，O(n log n). • ここでは次のことを学ぶ – heap(整列二分木）とは何か？ – それをどう表現するか？（データ構造） – これを使ってどうやってソートするのか？ 2003/5/6 ソフトウェア実習I 14 親（parent）と子（child） A 節点2の親 は節点1． 節点2は節 点1の子． 2003/5/6 F 1 E 2 ソフトウェア実習I 節点3の親 3 は節点1． 節点3は節 点1の子． 15 木(tree) 根(root) 節（node) 頂点(vertex) A C B D 節と節とを結ぶ線は 辺(edge)． E F G H 葉(leaf) 2003/5/6 ソフトウェア実習I 16 木(tree) level 0 X level 1 A level 3 W R F B 2003/5/6 C level 2 D •節点（node)の集合と辺(edge) の集合からなる． •節点には名前が付けられたり， 他の情報を持つことがある． •辺は２つの節点を結ぶ． •道（パス，path）とは互いに異 なる節点の並びであり並びの 中で隣り合う節点は辺で結ば れている． •根とそれ以外の任意の一つ の節点の間には一つだけ道が ある． ソフトウェア実習I 17 二分木(binary tree) •節点（node)から出る辺が最大 で２個の木． S E V A F D 2003/5/6 L C ソフトウェア実習I 18 完全二分木(complete binary tree)と 配列による表現 S E V 4 1 A 2 F 5 L 3 6 k [1][2] [3] [4][5][6] a[k] S E A V F L level 0 level 1 2003/5/6 •節点 i の親は i / 2で 求まる． •節点 j の子は2j, 2j+1 で求まる． •ただし，一番下のレベ ルは右が空いている 場合があるので，どこ まで節点があるかを記 憶する必要あり． •例えば節点3の子 は6だけ．7は無い． level 2 ソフトウェア実習I 19 完全二分木の配列表現上での操作 S E V A F L •一番下のレベルを除 いて，どのレベルも内 部節点が完全に埋 まっていて，一番下の レベルにある内部節点 が左に詰められている ものを完全二分木とこ こでは定義する． k [1][2] [3] [4][5] [6] a[k] S E A V F L level 0 level 1 2003/5/6 level 2 ソフトウェア実習I 20 整列二分木（heap）： heap条件を満たした完全二分木 2 1 5 4 heap条件： 親の中身が子の中身より大きい 1 3 2 6 5 4 3 heap条件を満たしていない木の例 6 k [1][2][3][4][5][6] a[k] 2 1 3 5 6 4 2003/5/6 ソフトウェア実習I 21 heap条件を満たすためのデータの入れ替え 2 1 5 4 1 3 2 6 5 4 3 6 k [1][2][3][4][5][6] a[k] 2 1 3 5 6 4 2003/5/6 downheap(int a[], int j, int k) { int i, v; v = a[j]; while (j <= k/2){ i = 2 * j; if(i<k && a[i]<a[i+1]) i++; if(v>=a[i])break; a[j]=a[i]; j=i; } a[j] = v; } downheap(a, 3, 6); downheap(a, 2, 6); downheap(a, 1, 6); ソフトウェア実習I 22 heap_sort内でのdownheapの呼び出し（１） 2 1 5 4 1 3 2 6 5 4 3 6 k [1][2][3][4][5][6] a[k] 2 1 3 5 6 4 v=3 2003/5/6 節点３と節点６の 中身を比較 downheap(int a[], int j, int k) { int i, v; v = a[j]; while (j <= k/2){ i = 2 * j; if(i<k && a[i]<a[i+1]) i++; if(v>=a[i])break; a[j]=a[i]; j=i; } a[j] = v; } downheap(a, 3, 6); 子の方が大 downheap(a, 2, 6); きいので交 downheap(a, 1, 6); 換 ソフトウェア実習I 23 heap_sort内でのdownheapの呼び出し（２） 2 1 5 4 1 4 2 6 5 3 3 6 k [1][2][3][4][5][6] a[k] v=1 2 1 4 5 6 3 downheap(int a[], int j, int k) { int i, v; v = a[j]; while (j <= k/2){ i = 2 * j; if(i<k && a[i]<a[i+1]) i++; if(v>=a[i])break; a[j]=a[i]; j=i; } a[j] = v; } downheap(a, 3, 6); downheap(a, 2, 6); downheap(a, 1, 6); vと節点５（４と５の大き 2003/5/6 い方）との中身を比較ソフトウェア実習I 子の方が大 きいので交 換 24 heap_sort内でのdownheapの呼び出し（３） 2 6 5 4 1 4 2 1 5 3 3 6 k [1][2][3][4][5][6] a[k] v=2 2 6 4 5 1 3 downheap(int a[], int j, int k) { int i, v; v = a[j]; while (j <= k/2){ i = 2 * j; if(i<k && a[i]<a[i+1]) i++; if(v>=a[i])break; a[j]=a[i]; j=i; } a[j] = v; } downheap(a, 3, 6); 子の方が大 downheap(a, 2, 6); きいので子 downheap(a, 1, 6); を親に移動 節点１と節点２（２と３の 2003/5/6 ソフトウェア実習I 大きい方）との中身を比較 25 heap_sort内でのdownheapの呼び出し（４） 6 5 5 4 1 4 2 1 5 3 3 6 k [1][2][3][4][5][6] a[k] v=2 6 6 4 5 1 3 downheap(int a[], int j, int k) { int i, v; v = a[j]; while (j <= k/2){ i = 2 * j; if(i<k && a[i]<a[i+1]) i++; if(v>=a[i])break; a[j]=a[i]; j=i; } a[j] = v; } downheap(a, 3, 6); 子の方が大 downheap(a, 2, 6); きいので５ downheap(a, 1, 6); を上に移す vと節点４（４と５の大きい 2003/5/6 ソフトウェア実習I 方）との中身を比較 26 heap_sort内でのdownheapの呼び出し（5） 6 5 2 4 1 4 2 1 5 3 3 6 k [1][2][3][4][5][6] a[k] v=2 6 5 4 2 1 3 2003/5/6 a[j]=v; downheap(int a[], int j, int k) { int i, v; v = a[j]; while (j <= k/2){ i = 2 * j; if(i<k && a[i]<a[i+1]) i++; if(v>=a[i])break; a[j]=a[i]; j=i; } a[j] = v; } downheap(a, 3, 6); downheap(a, 2, 6); downheap(a, 1, 6); ソフトウェア実習I 27 heapを使ったソート（関数heap_sort） 6 5 2 4 1 4 2 1 5 3 3 rootに最大値が入っている． これを一番後ろと交換し， 一番後ろを取り除いた木の 整列二分木を作成すれば、 小さい順にデータを整列さ せることができる． 6 k [1][2][3][4][5][6] a[k] 6 5 4 2 1 3 2003/5/6 ソフトウェア実習I 28 heapを使ったソート（関数heap_sort） 3 5 2 4 1 4 2 1 5 6 3 rootに最大値が入っている． これを一番後ろと交換し， 一番後ろを取り除いた木の 整列二分木を作成すれば、 小さい順にデータを整列さ せることができる． 6 k [1][2][3][4][5][6] a[k] 3 5 4 2 1 6 2003/5/6 ソフトウェア実習I 29 heapを使ったソート（関数heap_sort） 3 5 2 4 1 4 2 1 3 rootに最大値が入っている． これを一番後ろと交換し， 一番後ろを取り除いた木の 整列二分木を作成すれば、 小さい順にデータを整列さ せることができる． 5 k [1][2][3][4][5][6] a[k] 3 5 4 2 1 6 2003/5/6 ここから前 だけ考える downheap(a, 1, --k); ソフトウェア実習I 30 heapを使ったソート（関数heap_sort） 5 3 2 4 1 4 2 1 3 rootに最大値が入っている． これを一番後ろと交換し， 一番後ろを取り除いた木の 整列二分木を作成すれば、 小さい順にデータを整列さ せることができる． 5 k [1][2][3][4][5][6] a[k] 3 5 4 2 1 6 downheap(a, 1, --k); 以後同様に行えばよい！ 2003/5/6 ここから前 だけ考える ソフトウェア実習I 31 heap_sort内でのdownheapの呼び出し（５） 6 6 5 4 1 4 2 1 5 3 3 6 k [1][2][3][4][5][6] a[k] 6 6 4 5 1 3 downheap(int a[], int j, int k) { int i, v; v = a[j]; while (j <= k/2){ i = 2 * j; if(i<k && a[i]<a[i+1]) i++; if(v>=a[i])break; a[j]=a[i]; j=i; } 二回目のwhile a[j] = v; loop } downheap(a, 3, 6); 子の方が大 downheap(a, 2, 6); きいので６ downheap(a, 1, 6); を上に移す 節点１と節点２（２と３の 2003/5/6 ソフトウェア実習I 大きい方）との中身を比較 32 ソート方法のいろいろ • バブルソート：1年生の時、学んだ方法． メリットはほとんど無い．プロは使用しない． • 単純挿入法 • ヒープソート • クイックソート 2003/5/6 ソフトウェア実習I 33 クイックソート • 平均 O(n log n)，最悪の場合 O(n2)の手間． • 第1回の実習はこれを基にしている • pivot(軸）を選び、これより左側にはpivot以 下のものを，右側にはpivot以上のものを集 める．2分割、4分割、8分割と再帰的にこの 作業をすすめる． • 前回の資料を参考にして実際に簡単な例で 実行の様子を紙にかいて理解してからプロ グラムをすること． 2003/5/6 ソフトウェア実習I 34 課題について • 各ソート法の効率（スピードや手数）を計測する • 実際の時間を計るには time コマンドを使えば良い が、並べ替えるデータの個数が小さいと計測できな い．大きくし、さらにforループなどで行うこと • 入れ替えや代入の度にカウントアップする変数を用 意しこれによる手間の計測をすること • 並べ替えデータについては3種類程度考えること （なぜそれを選んだかの理由も必要）。 • データの個数ｎを大きくしていったときの変化の様 子もしらべること 2003/5/6 ソフトウェア実習I 35 リダイレクトとパイプライン # a.out < file1 # a.out > file2 # a.out <file1 >file2 # cat file1 file2 | sort | uniq > kekka # cat kekka 2003/5/6 ソフトウェア実習I 36
© Copyright 2024 ExpyDoc
