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

date2026-07-14document_iddoc_b23650bdaa56cb7caec56fbb7d34c2a6description整列の仕様、安定性、原位置性、比較モデルを定義し、挿入整列と併合整列の正当性および計算量を説明する。prerequisites計算量の基本 / 再帰の基本 / 配列の基本操作type講義statusactive

algorithmfoundationundergraduatelecture

data/lecture/information/algorithm/foundation/recursion-basics.lecture.n.md

1導入どうにゅう

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

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

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

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

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

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

3.1安定性あんていせい

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

3.2原位置性げんいちせい

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

3.3比較ひかくモデル

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

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

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

4.1正当性せいとうせい

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

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

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

4.2計算量けいさんりょう

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

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

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

5.1正当性せいとうせい

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

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

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

5.2計算量けいさんりょう

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

T (0) = T (1) = Θ (1), T (n) = T (⌊ n / 2 ⌋) + T (⌈ n / 2 ⌉) + Θ (n) (n \geq 2)

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

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

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

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

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

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

data/lecture/information/algorithm/search/binary-search.lecture.n.md

Sorting Basics

data/lecture/information/algorithm/foundation/recursion-basics.lecture.n.md

1Introduction

This lecture defines the specification and evaluation criteria of sorting and explains the correctness and complexity of insertion sort and merge sort. A sorted array is a prerequisite for the subsequent binary-search lecture.

2Sorting specification

Let $A = (a_{0}, \dots, a_{n - 1})$ be a sequence, and let a key function $k$ map each element to a totally ordered set. An ascending sorting algorithm produces $B = (b_{0}, \dots, b_{n - 1})$ satisfying both conditions below.

$B$ is a permutation of $A$ ; the multiplicity of every element is preserved.
$k (b_{0}) \leq k (b_{1}) \leq \dots \leq k (b_{n - 1})$ .

The first condition prohibits lost or duplicated elements, and the second specifies the output order.

3Evaluation criteria

3.1Stability

A stable sort preserves the relative output order of any two elements satisfying $i < j$ and $k (a_{i}) = k (a_{j})$ . This property preserves the result of an earlier sort when sorting by several keys in stages.

3.2In-place operation

An in-place sort updates the input array using $O (1)$ auxiliary space rather than an additional array proportional to $n$ . An analysis must state whether it includes recursive call-stack space.

3.3Comparison model

A comparison sort obtains information about keys only through results such as $k (x) \leq k (y)$ . Below, each comparison and assignment takes $O (1)$ time, and complexity denotes worst-case time unless stated otherwise.

4Insertion sort

Insertion sort takes $a_{i}$ for $i = 1, 2, \dots, n - 1$ and inserts it into its proper position in the sorted prefix $A [0, i)$ . It shifts right only elements whose keys are greater than the inserted key.

4.1Correctness

Use the following loop invariant: at the start of iteration $i$ , $A [0, i)$ contains exactly the original elements of that prefix in nondecreasing order.

For $i = 1$ , a one-element prefix is sorted.
Shifting elements greater than $a_{i}$ and inserting $a_{i}$ immediately before them preserves all elements and makes $A [0, i + 1)$ sorted.
At $i = n$ , the prefix is the entire array.

Thus insertion sort satisfies the sorting specification. It is stable because equal-key elements do not pass each other, and it is in-place because it requires only a temporary variable.

4.2Complexity

For an already sorted input, every iteration performs a constant number of comparisons, so the time complexity is $Θ (n)$ . In reverse order, insertion $i$ requires $i$ shifts, giving $\sum_{i = 1}^{n - 1} i = Θ (n^{2})$ total work.

5Merge sort

Merge sort divides a sequence until every part has length at most $1$ , recursively sorts the parts, and merges two sorted sequences. A merge compares their first remaining elements and transfers the smaller one to the output.

5.1Correctness

For merging, maintain the invariant that the produced sequence is sorted and contains exactly the elements removed from the two inputs. The smaller of the two first remaining elements is a minimum among all remaining elements, so appending it preserves the invariant. At termination, every element has been produced.

Induction on sequence length now proves the whole algorithm correct. Sequences of length $0$ or $1$ are trivially sorted. The inductive hypothesis gives two correctly sorted shorter sequences, and the correct merge produces a sorted permutation of the original sequence.

If equal keys are resolved by taking the left element first, merge sort is stable. A standard array implementation uses $O (n)$ auxiliary merge storage and is therefore not in-place.

5.2Complexity

Merging a total of $n$ elements takes $Θ (n)$ time. The time complexity $T (n)$ satisfies

T (0) = T (1) = Θ (1), T (n) = T (⌊ n / 2 ⌋) + T (⌈ n / 2 ⌉) + Θ (n) (n \geq 2) .

The recursion tree has height $⌈ \log_{2} n ⌉$ , and the subproblem lengths at any one depth sum to $n$ . Hence the merge cost at each depth is at most $O (n)$ , giving an $O (n \log n)$ upper bound. At every depth $0 \leq d < ⌊ \log_{2} n ⌋$ , subproblems of length at least $2$ have total length $Θ (n)$ , giving an $Ω (n \log n)$ lower bound. Therefore, $T (n) = Θ (n \log n)$ .

In a standard array implementation, a reusable merge array uses $Θ (n)$ space and the call stack uses $Θ (\log (n + 1))$ space. Thus, the total auxiliary-space complexity, including the call stack, is $Θ (n)$ . An empty sequence terminates immediately.

6Lower bound for comparison sorting

There are $n!$ input orders of $n$ elements with mutually distinct keys. The binary decision tree of a deterministic comparison sort needs at least $n!$ leaves to distinguish these orders, so its height is at least $⌈ \log_{2} (n!) ⌉$ . For $n \geq 2$ , the inequality $n! \geq (n / 2)^{n / 2}$ implies $\log_{2} (n!) = Ω (n \log n)$ . Hence every deterministic comparison sort requires $Ω (n \log n)$ comparisons in the worst case. Merge sort's $Θ (n \log n)$ bound is asymptotically optimal in this model.

7Connection to binary search

Binary search assumes $A_{0} \leq A_{1} \leq \dots \leq A_{n - 1}$ . For a single query on unsorted input, the cost of sorting may exceed its benefit. For repeated queries on the same array, sorting once in $O (n \log n)$ time and then performing each query in $O (\log n)$ time can be effective.

data/lecture/information/algorithm/search/binary-search.lecture.n.md