高速ソート
単純なソートアルゴリズム
バブルソート Ｏ（ｎ２）
選択ソート
Ｏ（ｎ２）
挿入ソート
Ｏ（ｎ２）
もっと高速なソートアルゴリズムは？
計算量が Ｏ（ｎ ｌｏｇ ｎ） のソートアルゴリズム
クイックソート
ヒープソート
マージソート
この中でクィックソートが最速
（ランダムデータに対して．不得手な場合もある）
クイックソートの原理
考え方： 分割統治法（ｄｉｖｉｄｅ ａｎｄ ｃｏｎｑｕｅｒ）
まず、配列中の適当な要素を選ぶ
→ これを枢軸（ｐｉｖｏｔ）と呼ぶ
次のように要素を並べ替える
→ これを分割（ｐａｒｔｉｔｉｏｎ）という
ａ［０］
・・・・・・・・・・ ａ［ｖ－１］ ａ［ｖ］ ａ［ｖ＋１］ ・・・ ａ［ｎ－１］
ａ［ｖ］より小（以下）
ａ［ｖ］
ａ［ｖ］より大（以上）
では、ａ［０］,・・・,ａ［ｖ－１］の部分と、
ａ［ｖ＋１］,・・・,ａ［ｎ－１］の部分は
どうするか？
↓
ピボットの選択
→分割を再帰的に繰り返せばよい！
クィックソートのアルゴリズム概観
①ソートするデータ区間のデータを得る
②区間内のデータ数が2以下の時
2-1：データ数が1以下の時なにもしない
2-2：データ数が２の時，必要なら交換
③区間内のデータ数が3以上の時
3-1:区間内でピボットを選ぶ（便宜的に右端）
3-2:区間内で，ピボットより小さい区間（左半
分）と大きい区間(右半分）に分割する
3-3:3-2の両区間を再帰的処理する
/* 配列ａのうち 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 ); /* 右の部分を整列する */
}
分割のアルゴリズム
０ａ．一番右の要素を枢軸に選ぶ
０ｂ．ポインタ ｉ を左端に、ポインタ ｊ を枢軸の
すぐ左に設定する
１．枢軸より大きな要素が見つかるまで
ｉ を右へスキャン
２．枢軸より小さな要素が見つかるまで
ｊ を左へスキャン
３． ｉ が指す要素と ｊ が指す要素を交換する
４． ｉ と ｊ がぶつかるまで１～３を繰り返す
５． ｊ の指す要素と枢軸と交換する
i
j
５５
３
７４
２０
１３
前半に＜３０，後半に＞３０を置く．それに反するものを入れ替える
５５
３
１３
４６
３０
j
２０
１３
８７
４６
３０
３
７４
j
２０
５５
８７
４６
３０
３
i
７４
５５
８７
４６
３０
５５
８７
４６
３０
j
２０
j
i
１３
８７
７４
i
１３
ピボット
３
２０
７４
左スキャンと右スキャンが交錯したらピボットをそこに置く→＠ピボットの左にピボットより小さい値，右に大きい値があるはず
j
１３
３
２０
ｖ
i
３０
５５
８７
４６
７４
再帰版クイックソート
/* 配列a[l]~a[r]を分割する。枢軸の添え字を返す */
int partition( int a[ ], int l, int r )
{
int i, j, pivot, t;
i = l – 1; j = r;
/* ポインタ i と ｊ を初期化する */
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 の指す要素と ｊ の指す要素を交換する */
}
t = a[i]: a［i］ = a[r]; a[r] = t; /* a[i] と枢軸を交換する */
return i;
｝
クイックソートの計算量
最適な分割：
ｐｉｖｏｔ がほぼ中央に来る
→ ほぼ半分ずつに分割される
→ 要素1までの分割数をｐとすると
２ｐ =n ，よってp=log 2n回分割が必要
部分列の個数はｎ個．
→ 計算量は Ｏ（ｎ ｌｏｇ ｎ）
最悪の分割：ピボット が端に来る
枢
軸
枢軸より小さい要素 ｋ－１個
↓
分割のレベル数（深さ）は ｎ
↓
計算量は Ｏ（ｎ２）
枢
軸
枢軸より大きい
要素 ０個
まとめ：
クイックソートの計算量は
最良 Ｏ（ｎ ｌｏｇ ｎ） 平均も！
最悪 Ｏ（ｎ２）
クイックソートの改善方法
部分配列の長さが１０程度以下になったら、
挿入ソートに切り替える
ｋ１・ｎ２ ＞？ ｋ２・ｎ ｌｏｇ２ｎ （ｋ１＜ｋ２）
俗に quicker sort
最悪の場合を回避する
部分配列の右端、中央、左端の３つのうちの
中央値を枢軸に
再帰の深さを減らす
→ 左右の部分配列のうち、
短いほうから先に処理をする
→ 再帰の深さは最大 ｌｏｇ２ｎ 程度
→ 非再帰版
→ 再帰の処理をスタックを利用して
自分で行なう。
安定結婚問題
安定結婚問題
フィーリングカップル5対5 （講義1回目）
１
２
３
①
②
③
４
④
５
⑤
安定結婚問題
・ 最初の論文 → [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)
不安定結婚とは
• カップルでない男女双方ともに互いに対する
好感度が自分のカップル相手よりも高い場合、
そのカップルは持続せず解消してしまう。
→不安定なカップル
• 上記の状況が全く発生していない
→安定なカップル
力任せで安定結婚問題を解くアルゴリズム
コンピュータは速いから、すべての5組カップルを生成して
（５！＝５＊４＊３＊２＊１＝１２０）、それが安定か不安定かを調べればいい？
N=11
1秒
N=１２
４秒
N=１３
2分52秒
N=１４
４2分３０秒
N=１５ １１時間
・すべての組み合わせを作る計算量は
・安定性をチェックする計算量は
・よって総計算量は
・N=16のときの大よその実行時間は
Ｎ！
Ｎ＊Ｎ
Ｎ！＊Ｎ＊Ｎ
1週間
もっと速いアルゴリズムは？
• なぜ遅い？
⇒すべての組合せを生成して，毎回浮気のチェックをしているので，
入力データ数Nの壁に阻まれる生成検査法（Generate and Test)
⇒一発で解が作れないか？
⇒それは無理
⇒でも無意味な組み合わせから始めるのはよくない
⇒どのような組合せなら作成可能で無駄が少ないか？
①理想的な状態（浮気が起こらない組合せ）から始めてみてはどうか？
理想状態＝第一希望の異性とのカップル
相手にパートナーがいるか否かを無視して、とりあえず強引に第一希望に
申し込む。既にパートナーがいれば、その好感度を比較して、既存パート
ナーの好感度が高ければ、申込を破棄、低ければ、パートナーを解消して、
新パートナーを作る。
もっと速いアルゴリズムは？
②乗り換え発生時：カップル解消された人は困りますよね。その
人は、一つ好感度が低い人に新たにカップルを申し入れて、
先程と同様の処理をする。
③カップル解消が起きて一人はじかれると、
入れ替え（玉突き現象）が際限なく起こらない？
⇒これは大丈夫。好感度が一つ低い相手を選ぶので、
一度のカップル解消で最大入れ替え回数は？回
下記の例で効率的アルゴリズムを実行してみると
男子
④③②⑤①
③②⑤①④
④②⑤③①
④⑤③①②
②③④①⑤
×
４１３２５
１３５２４
３５１２４
４２１３５
女子
手順１
男性１
④
手順２
男性１
④
男性２
③
男性１
④
男性２
③
男性３
④→２
？
．．．
？
．．．
手順３
手順４？
．．．
４３２１５
フィーリングカップル5対5 の解答
男子
④③②⑤①
③②⑤①④
④②⑤③①
④⑤③①②
②③④①⑤
×
４１３２５
１３５２４
３５１２４
４２１３５
４３２１５
女子
手順１ 男性１：④
手順２ 男性１：④ 男性２：③
手順３ 男性１：④ 男性２：③ 男性３：④→②
手順４ 男性１：④→③ 男性２：③→②→⑤ 男性３：④→② 男性４：④
手順５ 男性１：④→③→② 男性２：③→②→⑤→① 男性３：④→②→⑤
男性４：④ 男性５：②→③
より形式的に安定結婚問題を考えると
入力：男性N人
女性N人
希望リスト
N=5の例
男性： 1,2,3,4,5
女性： a,b,c,d,e
男性の希望リスト
女性の希望リスト
1:
a
c
b
d
e
a:
2
1
3
4
5
2:
c
a
e
b
d
b:
2
1
4
5
3
3:
b
a
e
d
c
c:
1
2
3
5
4
4:
c
b
d
e
a
d:
3
1
4
2
5
5:
c
d
b
e
a
e:
4
3
1
2
5
出力 ：男女間の不安定マッチングの例
1:
a
c
b
d
e
a:
2
1
3
4
5
12:
c
a
e
b
d
ab:
2
1
4
5
3
23:
b
a
e
d
c
bc:
1
2
3
5
4
34:
c
b
d
e
a
cd:
3
1
4
2
5
45:
c
d
b
e
a
de:
4
3
1
2
5
5 1 と女性 c は ブロッキングペア
e
男性
ブロッキングペアの存在しないマッチング: 安定マッチング
これは解の条件を満たしていない。
安定結婚問題: 与えられた入力から、安定マッチングを見つける。
The Gale-Shapley Algorithm [Gale & Shapley 1962]
(Men-propose）
1:
a
c
b
d
e
a:
2
1
3
×
2:
c
a
e
b
d
b:
2
1
4
e
d
c
c:
1
2
3
4:
b ×
a
×
c b
×
d
e
a
d:
3
1
4
2
5
5:
c
×
b
e
a
e:
4
3
1
2
5
3:
d
4
5
3
×
5 ×
4
×
5
Theorem [Gale & Shapley 1962, Gusfield & Irving 1989]
The Gale-Shapley algorithm finds a stable matching.
公開鍵暗号法
葉書の送り主
郵便局の職員
ラップトップ
葉書の受け取り人
Amazon.comのサーバー
インターネットのルーター
（および立ち聞きをする人）
葉書の比喩：郵便システムを通じて葉書を送ったとき､その内容の秘密を保つことはできな
い｡同じ理由から､ラップトップからＡｍａｚｏｎ.ｃｏｍに送ったクレジットカード番号は､適切に暗号
化されていなければ､悪意をもって立ち聞きしようとしている人に容易に覗かれてしまう。
共通鍵暗号法
329 - ? = ?
復号化不可能
イブ
共有された
秘密：322
7+322=329
符号化（暗号化）
されたメッセージ
あなた
共有された
秘密：322
329-322=7
復号化できて、
クレジット番号
がわかる
アーノルド
クレジット番号７
加算トリック:7というメッセージは､322という｢共有された秘密｣の数値との加算によって暗
号化される｡アーノルドは｢共有された秘密｣を引いて暗号を復号化できるが､イブはできない。
でもアーノルドが知人でなければ、彼だけに322を伝える手段がない！
公開部分
公開鍵暗号法(1)
公開色
イブ
あなたの
公開秘密
混合色
あなた
あなたの
秘密色
アーノルドの
公開秘密
混合色
アーノルド
アーノルドの
秘密色
?
公開色
あなた
あなたの
秘密色
あなたの
公開秘密
混合色
イブ
アーノルドの
公開秘密
混合色
共有された
秘密の混合色
共有された
秘密の混合色
白－緑－赤＝
青（アーノルド
の秘密色）が得
られる
白－青－赤＝
緑（あなたの秘
密色）が得られ
る
赤が2倍
になる
アーノルド
アーノルドの
秘密色
7
イブ
公開の数値
あなた
4
あなたの
秘密の数値
28
42
（4×7）
（6×7）
あなたの
公開秘密
混合値
アーノルドの
公開秘密
混合値
アーノルド
6
アーノルドの
秘密の数値
イブ
7
公開鍵暗号法(2)
公開の数値
あなた
4
あなたの
秘密の数値
28
42
（4×7）
（6×7）
あなたの
公開秘密
混合値
168
（4×6×7）
共有された
秘密値
６が得られる
アーノルドの
公開秘密
混合値
168
（4×6×7）
共有された
秘密値
４が得られる
割算ができないと
仮定すると、
２８と４２をかける
だけで、秘密の数値
はわからない
アーノルド
6
アーノルドの
秘密の数値
モジュロ（余りを求める）計算
0
6
1
5
2
4
3
0
6
1
5
2
4
3
左：サイズが7の時計を使うときには､12という数は5に単純化できる｡矢印が示すように､０
からスタートして時計回りに12単位分数えていけばよい｡右：再びサイズ7の時計を使うと、
12＋6＝4になる｡左の図の終点である5の位置を起点として､時計回りにさらに6単位分加
える。
％１１による計算
n
2n
3n
6n
1
2
3
6
2
4
9
3
3
8
5
7
4
5
4
9
5
10
1
10
6
9
3
5
7
7
9
8
8
3
5
4
9
6
4
2
10
1
1
1
この表は2、3、6の1乗から10乗までの値をサイズ11の時計算で示している。本文
で説明したように､個々の項目は1つ上の項目から非常に簡単な方法で計算できる。
公開鍵暗号法(3)
エリス＝コックス＝ウィリアムソン
デフィー＝ヘルマン＝マークル(1976)
11,2
3
（28 ）
あなた
8
あなたの
秘密の数値
イブ
公開の数値
あなたの
公開秘密
混合値
6
（29 ）
アーノルドの
公開秘密
混合値
アーノルド
9
アーノルドの
秘密の数値
実際に使われている数値混合のステップ3:累乗と時計算を使って計算した公開秘密混合
値(3と6)は､誰もが知ることができる｡3の下の28は､3がどのように計算されたかを思い出すた
めのメモだが､時計サイズ11で3＝28ということは公開されていない｡同様に､6の下の29も秘
密である。
11,2
公開鍵暗号法(3)
イブ
公開の数値
3
（28 ）
あなた
8
あなたの
秘密の数値
あなたの
公開秘密
混合値
6
（29 ）
アーノルドの
公開秘密
混合値
4
4
（6 ）
（3 ）
8
9
アーノルド
9
アーノルドの
秘密の数値
実際に使われている数値混合のステップ４:累乗と時計算を使って矢印で示された要素を結
合し「共有された秘密値｣を作れるのは､あなたとアーノルドだけ。
© Copyright 2024 ExpyDoc
