Presentation is loading. Please wait.

Presentation is loading. Please wait.

高速ソートと 安定結婚問題 平成24年12月14日.

Similar presentations


Presentation on theme: "高速ソートと 安定結婚問題 平成24年12月14日."— Presentation transcript:

1 高速ソートと 安定結婚問題 平成24年12月14日

2 高速ソート

3 単純なソートアルゴリズム バブルソート O(n2) 選択ソート O(n2) 挿入ソート O(n2) もっと高速なソートアルゴリズムは?
  バブルソート  O(n2)     選択ソート    O(n2)     挿入ソート    O(n2)   もっと高速なソートアルゴリズムは? 計算量が O(n log n) のソートアルゴリズム   クイックソート   ヒープソート   マージソート この中でクィックソートが最速 (ランダムデータに対して.不得手な場合もある)

4 クイックソートの原理 考え方: 分割統治法(divide and conquer) まず、配列中の適当な要素を選ぶ
   → これを枢軸(pivot)と呼ぶ 次のように要素を並べ替える    → これを分割(partition)という a[0]  ・・・・・・・・・・ a[v-1] a[v] a[v+1] ・・・ a[n-1] a[v]より小(以下) a[v] a[v]より大(以上)

5 では、a[0],・・・,a[v-1]の部分と、 a[v+1],・・・,a[n-1]の部分は どうするか?
では、a[0],・・・,a[v-1]の部分と、     a[v+1],・・・,a[n-1]の部分は どうするか?      ↓ ピボットの選択 →分割を再帰的に繰り返せばよい!

6 クィックソートのアルゴリズム概観 ①ソートするデータ区間のデータを得る
②区間内のデータ数が2以下の時 2-1:データ数が1以下の時なにもしない 2-2:データ数が2の時,必要なら交換 ③区間内のデータ数が3以上の時 3-1:区間内でピボットを選ぶ(便宜的に右端) 3-2:区間内で,ピボットより小さい区間(左半分)と大きい区間(右半分)に分割する 3-3:3-2の両区間を再帰的処理する

7 /* 配列aのうち a[l]~a[r] を整列する */
quick_sort ( int a[ ], int l, int r ) {   if( 整列する要素が一つのみである )     return;   適当な要素 a[v] を枢軸にして、     a[v] より小さい要素を a[l]~a[v-1] に集め、     a[v] より大きい要素を a[v+1]~a[r] に集める     quick_sort ( a, l, v-1 ); /* 左の部分を整列する */     quick_sort ( a, v+1, r ); /* 右の部分を整列する */ }

8 分割のアルゴリズム 0a.一番右の要素を枢軸に選ぶ 0b.ポインタ i を左端に、ポインタ j を枢軸の すぐ左に設定する
   すぐ左に設定する 1.枢軸より大きな要素が見つかるまで    i を右へスキャン 2.枢軸より小さな要素が見つかるまで    j を左へスキャン 3. i が指す要素と j が指す要素を交換する 4. i と j がぶつかるまで1~3を繰り返す 5. j の指す要素と枢軸と交換する

9 ピボット i j 55 74 20 13 87 46 30 前半に<30,後半に>30を置く.それに反するものを入れ替える j 55 74 20 13 87 46 30 i j 13 74 20 55 87 46 30 j i 13 74 20 55 87 46 30 j i 13 20 74 55 87 46 30 左スキャンと右スキャンが交錯したらピボットをそこに置く→@ピボットの左にピボットより小さい値,右に大きい値があるはず j i 13 20 30 55 87 46 74

10 再帰版クイックソート /* 配列a[l]~a[r]を分割する。枢軸の添え字を返す */ int partition( int a[ ], int l, int r ) { int i, j, pivot, t; i = l – 1; j = r; /* ポインタ i と j を初期化する */ pivot = a[r]; /* いちばん右端の要素を枢軸にする */ for( ; ; ) { /* ポインタ i と j とがぶつかるまで繰り返す */ while( a[++i] < pivot ) ; /* ポインタ i を右へ進める */ while( i < j && pivot < a[j] ) ; /* ポインタ i を左へ進める */ if ( i >= j ) break; /* ポインタ i と j がぶつかったらループを抜ける */ t = a[i]: a[i] = a[j]; a[j] = t; /* i の指す要素と j の指す要素を交換する */ } t = a[i]: a[i] = a[r]; a[r] = t; /* a[i] と枢軸を交換する */ return i;

11 クイックソートの計算量 最適な分割: pivot がほぼ中央に来る → ほぼ半分ずつに分割される
 pivot がほぼ中央に来る  → ほぼ半分ずつに分割される  → 要素1までの分割数をpとすると 2p =n ,よってp=log 2n回分割が必要    部分列の個数はn個.    → 計算量は O(n log n)

12 最悪の分割:ピボット が端に来る ↓ 分割のレベル数(深さ)は n 計算量は O(n2) 枢軸より大きい 要素 0個 まとめ:
最悪の分割:ピボット が端に来る      ↓ 分割のレベル数(深さ)は n 計算量は O(n2) 枢軸 枢軸より小さい要素 k-1個 まとめ:  クイックソートの計算量は   最良 O(n log n)  平均も!   最悪 O(n2)

13 クイックソートの改善方法 部分配列の長さが10程度以下になったら、 挿入ソートに切り替える 最悪の場合を回避する 中央値を枢軸に
 挿入ソートに切り替える    k1・n2 >? k2・n log2n  (k1<k2)     俗に quicker sort 最悪の場合を回避する     部分配列の右端、中央、左端の3つのうちの   中央値を枢軸に

14 再帰の深さを減らす   → 左右の部分配列のうち、      短いほうから先に処理をする        → 再帰の深さは最大 log2n 程度   → 非再帰版       →  再帰の処理をスタックを利用して          自分で行なう。

15 安定結婚問題

16 安定結婚問題 フィーリングカップル5対5 (講義1回目)
安定結婚問題 フィーリングカップル5対5 (講義1回目) 1 2 3 4 5 ① ② ③ ④ ⑤

17 安定結婚問題 ・ 最初の論文 → [Gale & Shapley 1962] - アメリカの研修医配属問題がきっかけ。
  - アメリカの研修医配属問題がきっかけ。   - どんな例題にも、必ず安定マッチングが存在する。   - 安定マッチングを多項式時間で見つけることができる。 (Gale-Shapley アルゴリズム) ・様々な類似問題 - 安定ルームメイト問題   - Residents/Hospitals 問題 ・最近、様々な新種の問題 ・実世界での応用   研修医配属   NRMP (National Resident Matching Program)   CaRMS (Canadian Resident Matching Service)   SPA (Scottish Pre-registration house officer Allocations) JRMP (Japanese Resident Matching Program)

18 不安定結婚とは カップルでない男女双方ともに互いに対する好感度が自分のカップル相手よりも高い場合、そのカップルは持続せず解消してしまう。 →不安定なカップル 上記の状況が全く発生していない →安定なカップル

19 力任せで安定結婚問題を解くアルゴリズム コンピュータは速いから、すべての5組カップルを生成して (5!=5*4*3*2*1=120)、それが安定か不安定かを調べればいい?
N=11         1秒 N=12        4秒 N=13  分52秒 N=14  42分30秒 N=15 11時間 ・すべての組み合わせを作る計算量は N! ・安定性をチェックする計算量は     N*N ・よって総計算量は             N!*N*N ・N=16のときの大よその実行時間は  1週間

20 もっと速いアルゴリズムは? なぜ遅い? ⇒すべての組合せを生成して,毎回浮気のチェックをしているので,   入力データ数Nの壁に阻まれる生成検査法(Generate and Test) ⇒一発で解が作れないか? ⇒それは無理 ⇒でも無意味な組み合わせから始めるのはよくない ⇒どのような組合せなら作成可能で無駄が少ないか? ①理想的な状態(浮気が起こらない組合せ)から始めてみてはどうか?   理想状態=第一希望の異性とのカップル   相手にパートナーがいるか否かを無視して、とりあえず強引に第一希望に申し込む。既にパートナーがいれば、その好感度を比較して、既存パートナーの好感度が高ければ、申込を破棄、低ければ、パートナーを解消して、新パートナーを作る。

21 もっと速いアルゴリズムは? ②乗り換え発生時:カップル解消された人は困りますよね。その人は、一つ好感度が低い人に新たにカップルを申し入れて、先程と同様の処理をする。 ③カップル解消が起きて一人はじかれると、 入れ替え(玉突き現象)が際限なく起こらない? ⇒これは大丈夫。好感度が一つ低い相手を選ぶので、 一度のカップル解消で最大入れ替え回数は?回

22 手順4? ... ? 下記の例で効率的アルゴリズムを実行してみると × ④③②⑤① ③②⑤①④ ④②⑤③① ④⑤③①② ②③④①⑤
41325 13524 35124 42135 43215 × 男子 女子 手順1 男性1 手順2 男性2 手順3 男性3 ④→2 手順4? ...

23 フィーリングカップル5対5 の解答 ④③②⑤① ③②⑤①④ ④②⑤③① ④⑤③①② ②③④①⑤ 41325 13524 35124 42135 43215 × 男子 女子 手順1 男性1:④ 手順2 男性1:④ 男性2:③ 手順3 男性1:④ 男性2:③ 男性3:④→② 手順4 男性1:④→③ 男性2:③→②→⑤ 男性3:④→② 男性4:④ 手順5 男性1:④→③→② 男性2:③→②→⑤→① 男性3:④→②→⑤ 男性4:④ 男性5:②→③

24 より形式的に安定結婚問題を考えると 入力:男性N人 女性N人 希望リスト N=5の例 男性: 1,2,3,4,5 女性: a,b,c,d,e
1: a c b d e a: 2: c a e b d b: 3: b a e d c c: 4: c b d e a d: 5: c d b e a e: 男性の希望リスト        女性の希望リスト

25 出力 :男女間の不安定マッチングの例 1: a c b d e a: 2: c a e b d b: 3: b a e d c c: 4: c b d e a d: 5: c d b e a e: a b c d e 男性 1 と女性 c は ブロッキングペア ブロッキングペアの存在しないマッチング:  安定マッチング これは解の条件を満たしていない。 安定結婚問題: 与えられた入力から、安定マッチングを見つける。

26 The Gale-Shapley Algorithm [Gale & Shapley 1962]
    (Men-propose) × 1: a c b d e a: 2: c a e b d b: 3: b a e d c c: 4: c b d e a d: 5: c d b e a e: × × × × × × × Theorem [Gale & Shapley 1962, Gusfield & Irving 1989]   The Gale-Shapley algorithm finds a stable matching.


Download ppt "高速ソートと 安定結婚問題 平成24年12月14日."

Similar presentations


Ads by Google