簡単な検索と整列（ソート）

Transcription

1 フローチャート (2) アルゴリズム論第 2 回講義 2011 年 10 月 7 日 ( 金 )

2 反復構造 ( 一定回数のループ処理 ) START 100 回同じ処理を繰り返す お風呂で子供が指をおって数を数える感じ 繰り返し数を記憶する変数をカウンター ( 変数名 I をよく使う ) と呼ぶ カウンターを初期化して, 100 回繰り返したかどうか判定してそうならば終了そうでなければ処理を実行して カウントアップ ( インクリメント ) して ~ に戻って同様の処理を続ける i=0 i = or >100 no 反復処理 i=i+1 END yes 前処理 終了条件判定 後処理

3 合計処理 ( 配列を使う ) 前提 :N 個のデータが予め配列 array に格納.(N は既知 ) 目標 : その個の数値データの合計値を sum に求める 変数 sum 前処理 何を初期化? i=0, sum=0 反復処理? 配列要素の添え字を利用 sum=sum+array(i) 終了条件は? 31 配列 array 後処理 何を出力?

4 合計処理 ( 配列 ) フローチャート START i=0,sum=0 前処理 i N yes no sum=sum+array(i) i=i+1 END 後処理

5 カウント処理 ( 配列を使う ) 前提 :N 個のデータが予め配列 array に格納 (N は不明 ). 末尾にデータ終了を表すためにー 1 が格納. 目標 : データの個数を変数 count に求める 変数 count データ個数 前処理 何を初期化? 反復処理? 配列要素の添え字を利用 終了条件は? 配列 array -1 データ末尾 後処理 何を出力?

6 カウント処理 ( 配列 ) フローチャート

7 合計値 データ個数 平均値 平均値算出 合計値を求めるアルゴリズムとデータ個数を求めるアルゴリズムを組み合わせれば, 平均値を求めるアルゴリズムが作成できるはず 前提 :N 個のデータが予め配列 array に格納 (N は不明 ). 末尾にデータ終了を表すためにー 1 が格納. 目標 : 所与データ群の平均値を変数 ave に求める 54 前処理 何を初期化? 平均値 変数 ave 反復処理? 配列要素の添え字を利用 31 終了条件は? -1 データ末尾 後処理 例外処理が必要 配列 array

8 平均値算出フローチャート

9 最大値選出 a b c つの変数,a,b,c に格納されている値から最大値を選ぶには? aとbを比較して, aが大きければ? bが大きければ? データが多くなると上記処理では対応できない. よって配列を利用して反復構造を適用する. N 個のデ タ 配列 array 暫定最大値 暫定最大値 前提 :N 個のデータが予め配列 array に格納 (N は既知 ). 目標 : 所与データ群からの最大値を変数 max に求める 31

10 最大値選出フローチャート

11 最小値選出 a b c N 個のデ タ 配列 array つの変数,a,b,c に格納されている値から最小値を選ぶには? aとbを比較して, aが小さければ? bが小さければ? 暫定最小値 データが多くなると上記処理では対応できない. よって配列を利用して反復構造を適用する. 暫定最小値 前提 :N 個のデータが予め配列 array に格納 (N は既知 ). 目標 : 所与データ群からの最小値を変数 min に求める 最大値選出と同様にできるが,99999 が array 配列要素より必ず大きいと仮定し,i=0 と初期化してフローチャートを作成せよ.

12 最小値選出フローチャート

13 開始 -1 max 101 min 0 sum 0 cnt cnt 10 ten を入力 a NO 問題 1: 10 人分の点数を入力し, 平均点, 最高点, 最低点を求める流れ図を示す. a と b を埋めよ YES 平均点 (=sum 10) を表示 最高点 (max) 最低点 (min) を表示 ten > max NO YES b 終了 ten < min YES NO ten min cnt + 1 cnt

14 開始 data を入力 data max data min 1 cnt 1 問題 2 入力データ :63, 82, 35, 92, 71, 32 流れ図の α は何回実行されるか? cnt 6 YES > data を入力 data:max 最高点 (max) を表示最低点 (min) を表示 < 終了 2 data max data:min α data min cnt +1 cnt

15 単純ソート 1 バブルソート 2 選択ソート 3 挿入ソート

16 ソート ( 並替え, 整列 ) アルゴリズム ランダムに並んでいるデータを 値の小さい順 ( 昇順 ), 大きい順 ( 降順 ) に並べ替えること 学生を学籍番号順, 都市を人口の多い順,...

17 コンピュータは Tunnel Vision トンネル視 ( 棒視, 視野狭窄症 ) 人間 : 一度に全体を見渡して判断できる コンピュータ : そんなグローバルな処理は ( 一度には ) できない. 2 つのデータの大小比較しかできない アセンブリ言語命令は, 一項演算か二項演算 局所的な処理を積み重ねてグローバルな処理を実現する この実現方法を考えることが, アルゴリズムを考えるということ

18 単純ソートの 2 つの基本処理 12 つのデータの大小比較 2( 逆順なら )2 つのデータを交換

19 バブルソート ( 隣接交換法 )

20 バブルソートのアルゴリズム 列の左端から始めて 1 隣接する 2 つのデータを比較. 2 左 > 右ならば入れ替え. 左 < 右ならそのまま. 3 右へ一つ移動して 2 を実行. 4 ソート済のデータに到達したら 3 を停止し, 左端に戻る.

21 4 要素のバブルソート a(0) a(1) a(2) a(3) a(0) a(1) a(2) a(3) 決 3 4 定 a(0) a(1) a(2) a(3) a(0) a(1) a(2) a(3)

22 バブルソートにおける 2 種類のループ処理 整列前 内部ループ (Inner Loop) : 反復操作 2 項比較比較範囲はインクリメンタル 隣接 2 データ比較 交換 外部ループ (Outer Loop): 反復操作 最大値を右端に追いやるスキャン ( 走査 ) 範囲はデクリメンタル

23 データ交換 a(2) a(3) a(2) の方が a(3) より大きいからデータを交換する a(2)=a(3) a(3)=a(2) とすると OK かな? だめ. バッファー ( 一時記憶 ) を使う b=a(2) a(2)=a(3) a(3)=b

24 a(0)a(1) a(9) 10 個のデータのソート 外部ループ 内部ループ start n=10 前処理 ( 初期化 ) 計算量をみるのは i=0 配列要素の比較と交換最後はa(8) とa(9) の比較 i>=n-1 今の走査 ( スキャン ) から抜け出す a(i)>a(i+1) 比較 no i++ yes b=a(i) a(i)=a(i+1) a(i+1)=b バブルソートの標準フローチャート 隣接データ交換処理大きい値がバッファを通して一つ右へ移動 インクリメンタル ( 隣接ペアを一つ右へずらす ) no n-- n<=1 デクリメンタル ( 走査範囲を一つ狭める ) yes stop

25 バブルソート ハンドシミュレーション 回目の処理結果? 回目の処理結果? 回目の処理結果? 回目の処理結果?

26 問題 1: 改良版バブルソート 1,2,3,4,5,6,7,8,910 のようなソート済みのデータだとどうなりますか? 上記をヒントにして 改良版 バブルソートの流れ図を示せ

27 バブルソート改良版の解答例 ソート済みか否かのフラグ変数を設け, 事前に 0 とし, 隣接データ交換処理をすればフラグ変 数を 1 に更新する. このようにすれば, 内部ループを抜け出した 時, フラグ変数をチェックし,0 であればソート済 みとして停止すればよい.

28 計算量 (Time Complexity)

29 計算量 あるアルゴリズムはどのくらい速いか? つまり 計算速度 ( 計算時間 ) は? コンピュータ OS 言語 コンパイラに依存する 計算の手数がデータの個数 n に対してどのように増えるか?

30 計算量 アルゴリズム A はアルゴリズム B の 2 倍速い という言い方ではだめなのか?( できないのか?) 扱うデータ数が変わると速度比も変わる場合があるため, あまり意味がない データ数 N と実行所要時間 T との間の 一般的な関係を知りたい

31 計算量 (2) O(n の関数 ) の形で表すこのとき 定数係数は無視する an 2 +bn+c O(n 2 ) オーダーというオーダーが違うオーダーが 1 桁違う

32 定数係数は無視する O(1) O(log n) O(n) O(n log n) O(n 2 ) O(n 3 ) O( 2 n ) 指数関数的 T( 時間 ) = K * 1/2(N 2 -N) = K/2 * N 2 -NK/2 多項式オーダー バブルソートの場合 K はプロセッサの速度など様々な現実状況をあらわしている O(n 2 )

33 ( 時間 ) 計算量 ビッグ O( オー ) 記法 O は Order の意味. アルゴリズムの実行時間は, コンピュータの性能に依存して変化する. 実行時間実測値よりも, データ数と実行時間 T の関係が重要 よって, 定数や低次項は無視して, 最大次数項に注目して, それをオーダーと呼び,O(~) と表記する. 記憶領域を議論するための領域計算量もあるが, ここでは時間計算量を計算量とよぶ.

34 ビッグオーのグラフ化 N O(2 n ) O(N 2 ) O(NlogN) O(N) O(logN) O(1)

35 O(2 n ) O(N 2 ) O(NlogN) ビッグオーの グラフ化 O(N) O(logN) O(1)

36 計算量の求め方 1. 各処理実行回数をデータ数 N で表現 2. 合計する 3. 最大次数に注目してビッグ O で表記. 問題左記の最大値選出アルゴリズムの計算量を求めよ.

37 バブルソートの計算量 ( オーダー ) 10,9,8,7,6,5,4,3,2,1 をバブルソートすると比較回数は? =45 交換回数は?9+8+7 =45 よって N 個のデータの場合問 1: 最大比較回数は?, 最大交換回数は? 問 2: 平均比較回数は?, 平均交換回数は? 問 3: 最小比較回数は?, 最小交換回数は?

38 N 個のデータのバブルソート 比較 交換 最大 平均 最小 (N-1)+(N-2)+ +1 =1/2N(N-1)=1/2(N 2 -N) O(N 2 ) ビッグオー記法 (N-1)+(N-2)+ +1 =1/2N(N-1)=1/2(N 2 -N) O(N 2 ) ビッグオー記法 (N-1)+(N-2)+ +1 =1/2N(N-1)=1/2(N 2 -N) O(N 2 ) ビッグオー記法 (N-1)+(N-2)+ +1 =1/2N(N-1)=1/2(N 2 -N) O(N 2 ) ビッグオー記法 ½*1/2(N 2 -N)=1/4(N 2 -N) O(N 2 ) ビッグオー記法 0