高速ソートと
安定結婚問題
高速ソート
単純なソートアルゴリズム
バブルソート Ｏ（ｎ２）
選択ソート
Ｏ（ｎ２）
挿入ソート
Ｏ（ｎ２）
もっと高速なソートアルゴリズムは？
計算量が Ｏ（ｎ ｌｏｇ ｎ） のソートアルゴリズム
クイックソート
ヒープソート
マージソート
この中でクィックソートが最速
（ランダムデータに対して．不得手な場合もある）
クイックソートの原理
考え方： 分割統治法（ｄｉｖｉｄｅ ａｎｄ ｃｏｎｑｕｅｒ）
まず、配列中の適当な要素を選ぶ
→ これを枢軸（ｐｉｖｏｔ）と呼ぶ
次のように要素を並べ替える
→ これを分割（ｐａｒｔｉｔｉｏｎ）という
ａ［０］
・・・・・・・・・・ ａ［ｖ－１］ ａ［ｖ］ ａ［ｖ＋１］ ・・・ ａ［ｎ－１］
ａ［ｖ］より小（以下）
ａ［ｖ］
ａ［ｖ］より大（以上）
では、ａ［０］,・・・,ａ［ｖ－１］の部分と、
ａ［ｖ＋１］,・・・,ａ［ｎ－１］の部分は
どうするか？
↓
ピボットの選択
→分割を再帰的に繰り返せばよい！
クィックソートのアルゴリズム概観
①ソートするデータ区間のデータを得る
②区間内のデータ数が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.
© Copyright 2024 ExpyDoc
