整列せいれつの基本きほん

1導入どうにゅう

この講義こうぎでは、整列せいれつの仕様しようと評価基準ひょうかきじゅんを定義ていぎし、挿入整列そうにゅうせいれつと併合整列へいごうせいれつの正当性せいとうせいおよび計算量けいさんりょうを説明せつめいする。整列済せいれつずみの配列はいれつは、後続こうぞくする二分探索にぶんたんさくの前提ぜんていとなる。

2整列せいれつの仕様しよう

要素列ようそれつ $$A=(a_0,\dots ,a_{n-1})$$A=(a_0,\ldots,a_{n-1}) と、要素ようその鍵かぎを全順序集合ぜんじゅんじょしゅうごうへ対応たいおうさせる関数かんすう $$k$$k を考かんがえる。昇順整列しょうじゅんせいれつは、出力列しゅつりょくれつ $$B=(b_0,\dots ,b_{n-1})$$B=(b_0,\ldots,b_{n-1}) が次つぎの二条件にじょうけんを満みたす算法さんぽうである。

1. $$B$$B は $$A$$A の置換ちかんである。すなわち、各要素かくようその個数こすうが保存ほぞんされる。
2. $$k\left(b_0\right)\le k\left(b_1\right)\le \cdots \le k\left(b_{n-1}\right)$$k(b_0)\leq k(b_1)\leq\cdots\leq k(b_{n-1}) が成立せいりつする。

第一条件だいいちじょうけんは要素ようその欠落けつらくや重複生成ちょうふくせいせいを禁止きんしし、第二条件だいにじょうけんは出力順序しゅつりょくじゅんじょを規定きていする。

3評価基準ひょうかきじゅん

3.1安定性あんていせい

安定あんていな整列せいれつは、$$i<j$$i<j かつ $$k\left(a_i\right)=k\left(a_j\right)$$k(a_i)=k(a_j) である二要素にようその相対順序そうたいじゅんじょを出力しゅつりょくでも保存ほぞんする。複数ふくすうの鍵かぎで段階的だんかいてきに整列せいれつする場合ばあい、この性質せいしつによって先さきの整列結果せいれつけっかを維持いじできる。

3.2原位置性げんいちせい

入力長にゅうりょくちょう $$n$$n に比例ひれいする別配列べつはいれつを使用しようせず、追加領域ついかりょういき $$O\left(1\right)$$O(1) で入力配列内にゅうりょくはいれつないを更新こうしんする整列せいれつを原位置整列げんいちせいれつという。再帰呼出さいきよびだしの記憶領域きおくりょういきを含ふくめるかは解析かいせきで明示めいじする。

3.3比較ひかくモデル

比較整列ひかくせいれつでは、鍵かぎに関かんする情報じょうほうを $$k\left(x\right)\le k\left(y\right)$$k(x)\leq k(y) などの比較結果ひかくけっかからだけ取得しゅとくする。以下いかでは一回いっかいの比較ひかくと代入だいにゅうを $$O\left(1\right)$$O(1) とし、最悪時さいあくじの時間計算量じかんけいさんりょうを評価ひょうかする。

4挿入整列そうにゅうせいれつ

挿入整列そうにゅうせいれつは、$$i=1,2,\dots ,n-1$$i=1,2,\ldots,n-1 の順じゅんに $$a_i$$a_i を取とり出だし、整列済せいれつずみの接頭辞せっとうじ $$A[0,i)$$A[0,i) の適切てきせつな位置いちへ挿入そうにゅうする。鍵かぎが挿入要素そうにゅうようそより大おおきい要素ようそだけを右みぎへ移動いどうする。

4.1正当性せいとうせい

反復開始時はんぷくかいしじに「$$A[0,i)$$A[0,i) は、元もとの $$A[0,i)$$A[0,i) の要素ようそを昇順しょうじゅんに整列せいれつした列れつである」を不変条件ふへんじょうけんとする。

• $$i=1$$i=1 では、一要素いちようその接頭辞せっとうじは整列済せいれつずみである。
• $$a_i$$a_i より大おおきい要素ようそを右みぎへ移動いどうし、その直前ちょくぜんへ $$a_i$$a_i を挿入そうにゅうすると、要素ようそを保存ほぞんしたまま $$A[0,i+1)$$A[0,i+1) が昇順しょうじゅんになる。
• $$i=n$$i=n では接頭辞せっとうじが配列全体はいれつぜんたいと一致いっちする。

したがって、挿入整列そうにゅうせいれつは整列せいれつの仕様しようを満みたす。同一鍵どういつかぎの要素ようそを追おい越こさないため安定あんていであり、一時変数いちじへんすうだけで実装じっそうできるため原位置げんいちである。

4.2計算量けいさんりょう

既すでに整列済せいれつずみなら各反復かくはんぷくの比較回数ひかくかいすうは定数ていすうであり、時間計算量じかんけいさんりょうは $$\mathrm{\Theta }\left(n\right)$$\Theta(n) である。逆順ぎゃくじゅんでは $$i$$i 番目ばんめの挿入そうにゅうに $$i$$i 回かいの移動いどうを要ようするため、合計ごうけいは $$\sum _{i=1}^{n-1}i=\mathrm{\Theta }\left(n^2\right)$$\sum_{i=1}^{n-1}i=\Theta(n^2) となる。

5併合整列へいごうせいれつ

併合整列へいごうせいれつは、列れつを長ながさが高々たかだか $$1$$1 になるまで二分にぶんし、各部分列かくぶぶんれつを再帰的さいきてきに整列せいれつした後あと、二ふたつの整列済せいれつずみ列れつを併合へいごうする。併合へいごうでは両列りょうれつの先頭せんとうを比較ひかくし、小ちいさい方ほうを出力しゅつりょくへ移うつす。

5.1正当性せいとうせい

併合へいごうでは、「出力済しゅつりょくずみの列れつは昇順しょうじゅんであり、両入力列りょうにゅうりょくれつから取とり除のぞいた要素ようそを過不足かふそくなく含ふくむ」を不変条件ふへんじょうけんとする。両先頭りょうせんとうの小ちいさい方ほうは未出力要素全体みしゅつりょくようそぜんたいの最小要素さいしょうようそであるため、この要素ようそを追加ついかしても不変条件ふへんじょうけんは保存ほぞんされる。終了時しゅうりょうじには全要素ぜんようそが出力しゅつりょくされる。

列長れつちょうに関かんする帰納法きのうほうを適用てきようすると、長ながさ $$0$$0 または $$1$$1 の列れつは自明じめいに整列済せいれつずみであり、短みじかい二列にれつの再帰結果さいきけっかと正ただしい併合へいごうから元もとの列れつも正ただしく整列せいれつされる。したがって算法全体さんぽうぜんたいが正当せいとうである。

同一鍵どういつかぎでは左側ひだりがわの要素ようそを先さきに出力しゅつりょくすれば安定性あんていせいを保持ほじできる。標準的ひょうじゅんてきな配列実装はいれつじっそうは併合用へいごうようの $$O\left(n\right)$$O(n) 領域りょういきを使用しようするため、原位置げんいちではない。

5.2計算量けいさんりょう

長ながさ $$n$$n の併合へいごうは $$\mathrm{\Theta }\left(n\right)$$\Theta(n) 時間じかんを要ようする。時間計算量じかんけいさんりょう $$T\left(n\right)$$T(n) は

を満みたす。再帰木さいきぎの高たかさは $$\lceil {\log }_{2}n\rceil$$\lceil\log_2 n\rceil であり、同一深度どういつしんどにある部分列長ぶぶんれつちょうの合計ごうけいは $$n$$n である。したがって各深度かくしんどの併合費用へいごうひようは高々たかだか $$O\left(n\right)$$O(n) であり、上界じょうかいは $$O\left(n\log n\right)$$O(n\log n) となる。また、$$0\le d<\lfloor {\log }_{2}n\rfloor$$0\leq d<\lfloor\log_2 n\rfloor の各深度かくしんどでは長ながさ $$2$$2 以上いじょうの部分列ぶぶんれつの合計長ごうけいちょうが $$\mathrm{\Theta }\left(n\right)$$\Theta(n) であるため、下界げかいは $$\mathrm{\Omega }\left(n\log n\right)$$\Omega(n\log n) となる。よって、$$T\left(n\right)=\mathrm{\Theta }\left(n\log n\right)$$T(n)=\Theta(n\log n) である。

標準的ひょうじゅんてきな配列実装はいれつじっそうでは、再利用さいりようする併合用配列へいごうようはいれつが $$\mathrm{\Theta }\left(n\right)$$\Theta(n)、呼出よびだしスタックが $$\mathrm{\Theta }\left(\log \right(n+1\left)\right)$$\Theta(\log(n+1)) の領域りょういきを使用しようする。したがって、呼出よびだしスタックを含ふくむ総補助空間計算量そうほじょくうかんけいさんりょうは $$\mathrm{\Theta }\left(n\right)$$\Theta(n) である。空列くうれつは直ただちに終了しゅうりょうする。

6比較整列ひかくせいれつの下界かかい

互たがいに異ことなる鍵かぎをもつ $$n$$n 個この要素ようそには $$n!$$n! 通とおりの入力順序にゅうりょくじゅんじょがある。決定的比較整列けっていてきひかくせいれつの二分決定木にぶんけっていぎは、これらを識別しきべつするために少すくなくとも $$n!$$n! 枚まいの葉はを必要ひつようとし、その高たかさは少すくなくとも $$\lceil {\log }_2(n!)\rceil$$\lceil\log_2(n!)\rceil である。$$n\ge 2$$n\geq2 では $$n!\ge (n/2{)}^{n/2}$$n!\geq(n/2)^{n/2} であるため、$${\log }_2(n!)=\mathrm{\Omega }\left(n\log n\right)$$\log_2(n!)=\Omega(n\log n) が成立せいりつする。したがって、任意にんいの決定的比較整列けっていてきひかくせいれつは最悪時さいあくじに $$\mathrm{\Omega }\left(n\log n\right)$$\Omega(n\log n) 回かいの比較ひかくを要ようする。併合整列へいごうせいれつの $$\mathrm{\Theta }\left(n\log n\right)$$\Theta(n\log n) はこの比較ひかくモデルで漸近的ぜんきんてきに最適さいてきである。

7二分探索にぶんたんさくへの接続せつぞく

二分探索にぶんたんさくは、$$A_0\le A_1\le \cdots \le A_{n-1}$$A_0\leq A_1\leq\cdots\leq A_{n-1} が成立せいりつする配列はいれつを前提ぜんていとする。未整列みせいれつの入力にゅうりょくに一度いちどだけ探索たんさくするなら、整列せいれつの費用ひようが利益りえきを上回うわまわる場合ばあいがある。同おなじ配列はいれつを反復探索はんぷくたんさくするなら、最初さいしょに $$O\left(n\log n\right)$$O(n\log n) で整列せいれつし、その後あとの各探索かくたんさくを $$O\left(\log n\right)$$O(\log n) で実行じっこうする構成こうせいが有効ゆうこうとなる。