ソートアルゴリズム

文章发布时间:

最后更新时间:

文章总字数:
5.2k

预计阅读时间:
24 分钟

挿入ソート

擬似コード

1
2
3
4
5
6
7
8
9
INSERTION-SORT(A, n)
    for i = 2 to n
        key = A[i]
        // A[i]をソート済みの部分配列A[1 : i - 1]に挿入する
        j = i - 1
        while j > 0 and A[j] > key
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = key

以下は単調減少順のINSERTION-SORT

1
2
3
4
5
6
7
8
INSERTION-SORT(A, n)
    for i = 2 to n
        key = A[i]
        j = i - 1
        while j > 0 and A[j] < key
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = key

ループ不変式

  1. 初期条件:
    ループ不変式がループの最初の繰返し（ の繰返し）の直前で成立していることを示すことから始める。
    このとき、部分配列 は唯一の要素 から成され、実際、元 は格納されていた要素と等しいので、この部分配列はトリビアルにソート済みである。
    よって、最初の繰返しの直前でループ不変式は真である。

  2. ループ内条件:
    ループ不変式をすべての繰返しの直前で真であることを示すため、
    1回の繰返しがループ不変式を維持することを確認する。
    for ループの本体が行っているのは、 を入れるべき場所が見つかるまで , をそれぞれ 1 つ右に移し（第 4〜7 行）、 空いた場所 に値を挿入する（第 8 行）。
    この結果、部分配列 は元 に格納されていた要素から構成されているが、すでにソートされている。
    for ループの次の繰返しのために の値を 1 増やす（incrementing）とループ不変式が維持される。

  3. 終了条件:
    最後に、ループの停止を調べる。ループ変数 は初期値が 2 で、各繰返しで 1 ずつ増加する。
    第 1 行での値が を超えれば、ループは停止する。つまり、 で停止し、部分配列 は、開始時点で に格納されていた要素がすべて含まれている。
    これらの要素はすでにソートされている。したがって、アルゴリズムは正当である。

解析

  1. 最悪の場合の定義 入力配列が降順に並んでいる場合、各要素を正しい位置に挿入するために、それ以前のすべての要素と比較する必要があります。このとき、最悪実行時間が生じます。

  2. 実行時間の解析 挿入ソートの実行時間 は、以下のループの各行のコストに基づいて計算されます。

    • 外側の for ループ (2行目から8行目): に対して実行されます。

    • 内側の while ループ (5行目から7行目): 最悪の場合、while ループは が配列 のすべての要素より小さい場合に実行され、比較と移動が 回行われます。

  3. 実行時間の式 各行のコストを とした場合、最悪の場合の実行時間は次のように表されます。

  4. 和の計算 以下の和を計算します。

    を計算：

    式 を用いると：

  5. 実行時間の整理 これを に代入すると：

    さらにまとめると：

  6. 線形関数としての表現 最悪の場合の実行時間は、以下のように表されます：

    ここで：

以上が、挿入ソートの最悪実行時間を導く過程です。この計算により、挿入ソートは最悪の場合において の計算量であることが示されます。

線形探索

擬似コード

以下は線形探索である

1
2
3
4
5
LINEAR-SEARCH(A, v)
    for i = 1 to A.length
       if A[i] == v
            return i
    return NIL

以下は2分探索である

反復:

1
2
3
4
5
6
7
8
9
ITERATIVE-BINARY-SEARCH(A, v, low, high)
    while low ≤ high
        mid = floor((low + high) / 2)
        if v == A[mid]
            return mid
        else if v > A[mid]
            low = mid + 1
        else high = mid - 1
    return NIL

再帰:

1
2
3
4
5
6
7
8
9
RECURSIVE-BINARY-SEARCH(A, v, low, high)
    if low > high
        return NIL
    mid = floor((low + high) / 2)
    if v == A[mid]
        return mid
    else if v > A[mid]
        return RECURSIVE-BINARY-SEARCH(A, v, mid + 1, high)
    else return RECURSIVE-BINARY-SEARCH(A, v, low, mid - 1)

選択ソート

擬似コード

1
2
3
4
5
6
7
8
SELECTION-SORT(A, n)
    n = A.length
    for i = 1 to n - 1
        minIndex = i
        for j = i + 1 to n
            if A[j] < A[minIndex]
                minIndex = j
        A[i]をA[minIndex]と交換する

最悪実行時間はである。

マージソート

擬似コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
MERGE(A, p, q, r)
    nL = q - p + 1      // A[p : q]の長さ
    nR = r - q      // A[q + 1 : r]の長さ
    L[0 : nL - 1]とR[0 : nR - 1]を新しい配列とする
    for i = 0 to nL - 1     // A[p : q]をL[0 : nL - 1]にコピーする
        L[i] = A[p + i]
    for j = 0 to nR - 1     // A[q + 1 : r]をR[0 : nR - 1]にコピーする
        R[j] = A[q + j + 1]
    i = 0   // iはLの中で最小の残っている要素のインデックスを登録する
    j = 0   // jはRの中で最小の残っている要素のインデックスを登録する
    k = p   // kはAを埋める場所のインデックスを登録する
    //各配列LとRがまだマージされていない要素を含む限り、まだマージされていない最小の要素をA[p : r]にコピーする
    while i < nL and j < nR
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else A[k] = R[j]
            j = j + 1
        k = k + 1
    // LかRの1つを完全に処理したので、もう1つの残りをA[p : r]の最後にコピーする
    while i < nL
        A[k] = L[i]
        i = i + 1
        k = k + 1
    while j < nR
        A[k] = R[j]
        j = j + 1
        k = k + 1
1
2
3
4
5
6
7
8
MERGE-SORT(A, p, r)
    if p >= r   // 0個か1個の要素？
        return
    q = floor((p + r)/2)    // A[p : r]の中点
    MERGE-SORT(A, p, q)   // 再帰的にA[p : q]をソート
    MERGE-SORT(A, q + 1, r)   // 再帰的にA[q + 1 : r]をソート
    // A[p : q]とA[q + 1 : r]をマージしてA[p : r]へ戻す
    MERGE(A, p, q, r)

以下はセンチネルを使用せずのMERGE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
MERGE(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q
    L[0 : n1 - 1]とR[0 : n1 - 1]を新しい配列とする
    for i = 1 to n1
        L[i] = A[p + i - 1]
    for j = 1 to n2
        R[j] = A[q + j]
    i = 1
    j = 1
    for k = p to r
        if i > n1
            A[k] = R[j]
            j = j + 1
        else if j > n2
            A[k] = L[i]
            i = i + 1
        else if L[i] ≤ R[j]
            A[k] = L[i]
            i = i + 1
        else
            A[k] = R[j]
            j = j + 1

解析

以下は、マージソート(Merge Sort)の最悪実行時間について、簡単に説明します。

  1. マージソートの基本動作

    1. 分割(Divide)
      配列を半分に分割し、各部分を再帰的にソートします。この操作は配列サイズが の場合、分割の深さが レベルになります。

    2. 統治(Conquer)
      各部分配列を結合（マージ）してソート済みの配列を作成します。各レベルで配列全体にわたってマージ操作を行うので、各レベルのコストは です。

  2. 再帰的な式の構築 分割と結合を考慮すると、マージソートの実行時間 は以下のような再帰式で表されます：

    • ：配列を2つに分割し、それぞれの部分配列をソートする時間。
    • ：現在のレベルでのマージ操作に必要な時間。

  3. 再帰式の解法

    1. 再帰式を展開すると、分割の深さごとにコストを計算できます。
    2. 再帰の深さは レベルであり、各レベルのコストは です。
    3. すべてのレベルのコストを合計すると：

  4. 最悪実行時間の結論 最悪実行時間は再帰的分割と統治に基づき、次のように表されます：

バブルソート

擬似コード

1
2
3
4
5
BUBBLESORT(A, n)
    for i = 1 to n - 1
        for j = n downto i + 1
            if A[j] < A[j - 1]
                A[j]とA[j - 1]を交換する

ループ不変式

  1. 行2 ~ 4のforループ 行2-4の for ループの各繰り返しの開始時点で、部分配列 は、ループ開始前に に存在していた要素から構成されますが、その順序は変わっている可能性があります。 ただし、先頭の要素 はその部分配列内で最小の要素です。

    1. 初期条件:
      初期状態では、部分配列 は最後の要素のみを含んでおり、この要素は自明的に部分配列内の最小要素です。

    2. ループ内条件:
      各ステップで と を比較し、 をその部分配列内で最小の要素にします。ループの繰り返し後、部分配列の長さは1つ増加し、先頭の要素は依然としてその部分配列内で最小の要素です。

    3. 終了条件:
      ループは のとき終了します。ループ不変式によると、 は 内で最小の要素であり、 はループ開始前の に存在していた要素から構成されています。

  2. 行1 ~ 4のforループ 行1-4の for ループの各繰り返しの開始時点で、部分配列 は、 内の 個の最小要素で構成され、昇順に整列されています。 一方、 は 内の残りの 個の要素で構成されています。

    1. 初期条件:
      初期状態では、部分配列 は空であり、自明的に部分配列内の最小要素が含まれています。

    2. ループ内条件:

    1. の結果から、内側のループの実行後、 は部分配列 内で最小の要素になります。そして外側のループ開始時点では、 は の要素より小さい要素から構成され、昇順に整列されています。 したがって、外側のループの実行後、部分配列 は の要素より小さい要素から構成され、昇順に整列されます。
    1. 終了条件:
      ループは のとき終了します。この時点で配列 はすべての要素を含み、昇順に整列されています。

ヒープソート

ヒープ条件の維持

擬似コード

1
2
3
4
5
6
7
8
9
10
11
MAX-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    if l <= heap-size[A] and A[l] > A[i]
        largest = l
    else largest = i
    if r <= heap-size[A] and A[r] > A[largest]
        largest = r
    if largest != i
        A[i]をA[largest]と交換する
        MAX-HEAPIFY(A, largest)

MIN-HEAPIFYバージョン

1
2
3
4
5
6
7
8
9
10
11
MIN-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    if l ≤ A.heap-size and A[l] < A[i]
        smallest = l
    else smallest = i
    if r ≤ A.heap-size and A[r] < A[smallest]
        smallest = r
    if smallest != i
        A[i]をA[smallest]と交換する
        MIN-HEAPIFY(A, smallest)

再帰の代わりに繰り返し構造子 (ループ) を使うバージョン

1
2
3
4
5
6
7
8
9
10
11
12
13
MAX-HEAPIFY(A, i)
    while true
        l = LEFT(i)
        r = RIGHT(i)
        if l ≤ A.heap-size and A[l] > A[i]
            largest = l
        else largest = i
        if r ≤ A.heap-size and A[r] > A[largest]
            largest = r
        if largest == i
            return
        A[i]をA[largest]と交換する
        i = largest

解析

  1. 操作の流れ MAX-HEAPIFYは、与えられた節点 を根とする部分木が max ヒープ条件を満たすように調整する操作です。この操作の流れは以下の通りです：

    1. 比較と選択:
      節点 の値をその左右の子（ および ）の値と比較し、3つの中で最大の値を持つ節点を特定します。

    2. 交換と再帰呼び出し:
      最大値を持つ節点が ではない場合、節点 とその最大値を持つ子を交換します。その後、交換によって影響を受けた子部分木に対して再帰的に MAX-HEAPIFY を呼び出します。

  2. 実行時間の解析:

    • 1回の呼び出しのコスト:
      1回の比較操作(左右の子と比較)にかかる時間は定数時間 です。ただし、交換後に再帰的に操作を繰り返すため、実行時間は部分木の高さに依存します。

    • 再帰関係:
      再帰的な呼び出しに基づく実行時間は以下の漸化式で表されます： ここで、 は、節点 の2つの子のうち、より大きな部分木のサイズを示します。

    • 解法と結論:
      マスター定理（画像の参照）を適用すると、この漸化式の解は： となります。したがって、MAX-HEAPIFY の最悪実行時間は木の高さ（）に比例します。

ヒープの構築

擬似コード

1
2
3
4
BUILD-MAX-HEAP(A, n)
    A.heap-size = n
    for i = floor(n/2) downto 1
        MAX-HEAPIFY(A, i)

MAX-HEAP-INSERTを呼び出しバージョン

1
2
3
4
BUILD-MAX-HEAP`(A)
    A.heap-size = 1
    for i = 2 to A.length
        MAX-HEAP-INSERT(A, A[i])

解析

ループ不変式

ループ不変式の定義:
for ループ(行2 - 3)の各繰り返しの開始時点で、各節点 は max ヒープの根である。

  1. 初期条件:
    ループの最初の繰り返しの直前では、 である。
    このとき、 は葉ノードであり、葉ノードは自明的に max ヒープの根である。したがって、ループ不変式は成立する。

  2. ループ内条件:
    各繰り返しで、節点 の左右の子を根とする部分木に対して MAX-HEAPIFY を呼び出す。この操作により、節点 を根とする部分木が max ヒープ条件を満たすようになる。
    さらに、次の繰り返しでは が 1 減少するため、ループ不変式は維持される。

  3. 終了条件:
    手続きは で終了する。ループ不変式によれば、終了時点で各節点 が max ヒープの根である。したがって、配列全体が max ヒープになっている。

実行時間

  1. MAX-HEAPIFY のコスト:
    MAX-HEAPIFY の実行時間は節点の高さに比例し、最悪の場合 です。

  2. 控える必要な事実:

    1. 高さ の節点数はおおよそ 個です。
    2. n個節点を含むヒープの深さはおおよそ である。

  3. 全体のコスト:
    BUILD-MAX-HEAP のコストは、すべての節点に対して MAX-HEAPIFY を適用する際の時間の合計です。この合計は以下のように表されます： 公式を用いると:

  4. 漸近的評価:
    付録の公式（図中の式）を用いると、この和は定数に収束することが示されます。したがって：

ヒープソートアルゴリズム

擬似コード

1
2
3
4
5
6
HEAPSORT(A, n)
    BUILD-MAX-HEAP(A, n)
    for i = n downto 2
        A[1]をA[i]と交換する
        A.heap-size = A.heap-size - 1
        MAX-HEAPIFY(A, 1)

解析

ループ不変式

  1. 初期条件:
    部分配列 は空であるため、この時点でループ不変式は成立している。

  2. 維持条件:
    は部分配列 の中で最大の要素であり、 の要素よりも小さい。
    この要素を位置 に移動させることで、部分配列 は最大の要素を含み、整列されている。
    ヒープのサイズを減らし、MAX-HEAPIFY を呼び出すことで、部分配列 が再び max ヒープになる。
    その後、 をデクリメントすることで、次の繰り返しに対するループ不変式が整備される。

  3. 終了条件:
    ループが終了するとき、 である。
    この時点で、部分配列 は整列済みであり、 は配列内で最小の要素である。
    したがって、配列全体 は整列されている。

実行時間

BUILD-MAX-HEAPの呼出しに時間かかり、1回の呼出しに時間かかるMAX-HEAPIFYが回呼び出されるので、手続きHEAPSORTの実行時間はである。

クイックソート

擬似コード

1
2
3
4
5
6
QUICKSORT(A, p, r)
    if p < r
        // ピボットを中心に部分配列を分割する。ピボットは最終的にA[q]で終わる
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q - 1)  // 下側を再帰的にソート
        QUICKSORT(A, q + 1, r)  // 上側を再帰的にソート
1
2
3
4
5
6
7
8
9
PARTITION(A, p, r)
    x = A[r]    // ピボット
    i = p - 1   // 下側で最大のインデックス
    for j = p to r - 1  // ピボット以外の各要素を処理
        if A[j] <= x    // この要素は下側に属する？
            i = i + 1   // 下側の新しいスロットのインデックス
            A[i]をA[j]と交換する    // この要素をそこに置く
    A[i + 1]をA[r]と交換する    // ピボットは下側のすぐ右に移動
    return i + 1    // ピボットの新しいインデックス

以下はHOAREの最初のPARTITIONアルゴリズム

1
2
3
4
5
6
7
8
9
10
11
12
13
14
HOARE-PARTITION(A, p, r)
    x = A[p]
    i = p - 1
    j = r + 1
    while TRUE
        repeat
            j = j - 1
        until A[j] <= x
        repeat
            x = x + 1
        until A[x] >= x
        if x < y
            A[i]をA[j]と交換する
        else return j

乱択版擬似コード

1
2
3
4
5
RANDOMIZED-QUICKSORT(A, p, r)
    if p < r
        q = RANDOMIZED-PARTITION(A, p, r)
        QUICKSORT(A, p, q - 1)
        QUICKSORT(A, q + 1, r)
1
2
3
4
RANDOMIZED-PARTITION(A, p, r)
    i = RANDOM(p, r)
    A[r]をA[i]と交換する
    return PARTITION(A, p, r)

解析

ループ不変式

行 3 - 4 の各繰り返しの開始時点で、部分配列 は 以下の値を含み、 は より大きい値を含む。 は未確認の値で構成され、 はピボット値 である。

  1. 初期条件 ループの最初の繰り返しの直前では、 かつ である。このとき、部分配列 と は空であるため、ループ不変式が成立する。

  2. 維持条件 各繰り返しで、次の 2 つの場合を考える：

    1. の場合:
      この場合、 を単に 増加させる。これにより、 は に加えられることなく より大きい部分に残り、ループ不変式が維持される。

    2. の場合:
      この場合、 を 増加させた後、 と を交換する。この操作により、 は に追加され、 以下の値として正しい位置に収まる。結果としてループ不変式が維持される。

  3. 終了条件 ループは で停止する。この時点で、 は空となり、配列全体は次の 3 つの部分に分割されている：

    • ： 以下の値。
    • ： より大きい値。
    • ：ピボット値 。

ピボット値を正しい位置 に移動することで、PARTITION 手続きは完了し、部分配列 が適切に分割される。

最悪実行時間

  1. 漸化式 QUICKSORT の最悪実行時間は、分割が極端に偏った場合（片側にすべての要素が集中するケース）に発生します。この場合、漸化式は次のように表されます： ここで、 は部分配列の要素数を示します。

  2. 最悪ケース 最悪ケースでは、分割が片側に極端に偏るため、 または となります。この場合の漸化式は：

  3. 漸化式の解 上記の漸化式を展開すると：

    最後の和は等差数列であるため：

期待実行時間

  1. 分割の期待ケース RANDOMIZED-QUICKSORT は、ランダムにピボットを選択することで、分割がほぼ均等になるように設計されています。このアルゴリズムの期待実行時間を解析するには、次の漸化式を考えます： ただし、ランダム性を考慮すると、分割が偏りにくいため、 に近いケースが期待されます。

  2. 比較回数の期待値

    • 補題: 任意の2つの要素と (i < j) が与えられたとき、この2つの要素が比較される確率はである。 証明： とが比較されるまたはがから選ばれる最初のピボット がから選ばれる最初のピボットがから選ばれる最初のピボット
    • 比較回数 をランダム変数として、指標確率変数をとが比較されると定義する。
    • 以上より、になっている。
    • 期待値 は次のように評価されます： とが比較される 補題を用いると： 変数を に変換し、調和数の公式を用いると：

  3. 結論 ランダム性によって分割のバランスが期待されるため、RANDOMIZED-QUICKSORT の期待実行時間は次のように評価されます：

計数ソート

擬似コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
COUNTING-SORT(A, n, k)
    B[1 : n]とC[0 : k]を新しい配列とする
    for i = 0 to k
        C[i] = 0
    for j = 1 to n
        C[A[j]] = C[A[j]] + 1
    // C[i]はiに等しい要素の個数を持っている
    for i = 1 to k
        C[i] = C[i] + C[i - 1]
    // C[i]はi以下の要素の数を示す
    // AはBにコピーし、Aの最後から始める
    for j = n downto 1
        B[C[A[j]]] = A[j]
        C[A[j]] = C[A[j]] - 1   // 重複する値の扱い
    return B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
MODIFIED-COUNTING-SORT(A, n, k)
    let C[0..k] be a new array
    for i = 1 to k
        C[i] = 0
    for j = 1 to n
        C[A[j]] = C[A[j]] + 1
    for i = 2 to k
        C[i] = C[i] + C[i - 1]
    insert sentinel element NIL at the start of A
    B = C[0..k - 1]
    insert number 1 at the start of B
    // B now contains the "endpoints" for C
    for i = 2 to n
        while C[A[i]] != B[A[i]]
            key = A[i]
            exchange A[C[A[i]]] with A[i]
            while A[C[key]] == key // make sure that elements with the same keys will not be swapped
                C[key] = C[key] - 1
    remove the sentinel element
    return A

解析

実行時間

計数ソートの実行時間を検討する。 第2 ~ 3行のforループに時間、第4 ~ 5行のforループに時間、第7 ~ 8行のforループに時間、 そして第11 ~ 13行のforループに時間がかかる。 したがって、全体の実行時間はである。通常のとき、計数ソートを用いる。実際には実行時間はである。

基数ソート

擬似コード

1
2
3
RADIX-SORT(A, n, d)
    for i = 1 to d
        安定ソートを用いて第i桁に関して配列A[1 : n]をソートする　

解析

補題 8.3

個の 桁の数が与えられていて、各桁が取りうる値の数が 以下であると仮定する。サブルーチンとして用いる安定ソートの実行時間が ならば、Radix-Sort はこれらの数を次の時間でソートする：

証明
Radix-Sort の正当性はソートされている列に関する帰納法によって示すことができる（練習問題 8.3-3 を参照）。
実行時間の解析は中間ソートとして用いる安定ソートに依存する。
各桁のうち 0 から の範囲にあり（それぞれ 個の値を取りうる）、各桁のソートは 時間を必要とする。
この操作を 桁すべてに対して実行するため、全体の実行時間は：

となる。

補題 8.4

個の 桁の数が与えられていて、各桁の数を -ビットで表現する。サブルーチンとして Counting-Sort を使用する場合、Radix-Sort の総実行時間は次の式で与えられる：

証明
値を各桁に対して、各キーを -ビットで表現した場合における次のような実行時間を考える。

  1. 各桁あたりの取りうる値の数を とする。

  2. サブルーチン Counting-Sort の実行時間は であり、これは各桁ごとのコストを決定する。

  3. 全体の桁数 に基づき、Radix-Sort の実行時間は：

  4. 条件 を満たすとき、実行時間は に近くなる。

したがって、総実行時間は次の式で表される：

バケツソート

擬似コード

1
2
3
4
5
6
7
8
9
10
BUCKET-SORT(A, n)
    B[0 : n - 1]を新しい配列とする
    for i = 0 to n - 1
        B[i]を空リストに初期化する
    for i = 1 to n
        A[i]をリストB[floor(n * A[i])]に挿入する
    for i = 0 to n - 1
        リストB[i]を挿入ソートでソートする
    リストB[0], B[1], ..., B[n - 1]をこの順序で連接する
    return 連結されたリスト

解析

実行時間

  1. 実行時間の分解 バケットソートの実行時間を解析するため、以下の2つの部分に分けて考える：
    1. 第7行以外の実行時間は、最悪の場合でも 時間である。
    2. 第7行の挿入ソートにかかる実行時間は、各バケット内の要素数 に依存する。
  2. 全体の実行時間 挿入ソートは 2 次の多項式時間で動作するため、バケットソート全体の実行時間 は以下の式で表される：

平均時の実行時間の期待値

  1. 期待値の計算

    期待値を計算する際、入力分布の一様性に基づき、期待値の線形性を適用する：

  2. 各バケットの要素数 の期待値

    各バケットに要素が均等に割り振られると仮定すると：

結論

バケットソートの期待実行時間は以下のように評価される：

線形期待時間選択アルゴリズム

擬似コード

1
2
3
4
5
6
7
8
9
10
RANDOMIZED-SELECT(A, p, r, i)
    if p == r
        return A[p] // 1 ≤ i ≤ r − p + 1 は p == r が i = 1 である。
    q = RANDOMIZED-PARTITION(A, p, r)
    k = q − p + 1
    if i == k
        return A[q] // このピボットの値が答えである
    elseif i < k
        return RANDOMIZED-SELECT(A, p, q − 1, i)
    else return RANDOMIZED-SELECT(A, q + 1, r, i − k)

以下は反復バージョン

1
2
3
4
5
6
7
8
9
10
PARTITION(A, p, r)
    x = A[r]
    i = p
    for k = p - 1 to r
       if A[k] < x
           i = i + 1
           swap A[i] with A[k]
    i = i + 1
    swap A[i] with A[r]
    return i
1
2
3
4
RANDOMIZED-PARTITION(A, p, r)
    x = RANDOM(p - 1, r)
    swap A[x] with A[r]
    return PARTITION(A, p, r)
1
2
3
4
5
6
7
8
9
10
11
12
13
RANDOMIZED-SELECT(A, p, r, i)
    while true
        if p == r
            return A[p]
        q = RANDOMIZED-PARTITION(A, p, r)
        k = q - p + 1
        if i == k
            return A[q]
        if i < k
            r = q - 1
        else
            p = q + 1
            i = i - k

解析

定理 9.2

個の異なる要素からなる入力配列に対する手続き RANDOMIZED-SELECT の期待実行時間は以下である：

証明

  1. 分割が有用である確率の定義 有用な分割とは、分割が進むたびに要素の集合が十分に減少する分割を指す。各分割について次のように定義する：

    • 集合のサイズ：（世代 における集合）。
    • 次の分割後の集合サイズ：。

    ここで： を定義する。つまり、 は世代 における分割後の集合の個数を表す。

  2. 分割の有効性と確率

    • 分割が有用である確率は少なくとも 1/2 である。
    • このとき、分割のたびに集合のサイズは 以下に縮小する（ は元の入力配列サイズ）。

  3. 期待値の計算 分割が有効である場合に、比較回数の期待値を計算する：

    ここで であることから：

結論

等比数列の和を用いて整理すると：

したがって、RANDOMIZED-SELECT の期待実行時間は次のように評価される：

線形最悪時間選択アルゴリズム

擬似コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
SELECT(A, p, r, i)
    while (r − p + 1) mod 5 != 0
        for j = p + 1 to r
            if A[p] > A[j] // 最小値を A[p] に置く
                A[p] を A[j] と交換する
        // A[p:r] の最小値が得られれば、これで終わり
        if i == 1
            return A[p]
        // そうでなければ、A[p + 1:r] の (i − 1) 番目の要素を得たい
        p = p + 1
        i = i − 1
    g = (r − p + 1) / 5     // 5 要素のグループの個数
    for j = p to p + g − 1  // 各グループをソート
        <A[j], A[j + g], A[j + 2g], A[j + 3g], A[j + 4g]> をその場でソートする
    // すべてのグループ中央値が、今ではA[p : r]の中央の5番目にある
    x = SELECT(A, p + 2g, p + 3g − 1, ceiling(g/2))
    q = PARTITION-AROUND(A, p, r, x)    // ピボットに関して分割
    // 残りは RANDOMIZED-SELECT の第3 ~ 9行とまったく同じである
    k = q + p + 1
    if i == k
        return A[q]     // ピボットの値が答えである
    elseif i < k
        return SELECT(A, p, q − 1, i)
    else return SELECT(A, q + 1, r, i − k)

以下は3グループのバージョン

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
SELECT3(A, p, r, i)
    while (r - p + 1) mod 9 != 0
        for j = p + 1 to r      // 最小値を A[p] に置く
            if A[p] > A[j]
                A[p] を A[j] で置き換える
        // A[p : r] の最小値を求めることが目的なら、ここで終了
        if i == 1
            return A[p]
        // そうでなければ、A[p + 1 : r] の (i - 1) 番目の要素がほしい
        p = p + 1
        i = i - 1
    g = (r - p + 1) / 3     // 3 要素のグループの個数
    for j = p to p + g - 1  // グループを通して調べる
        <A[j], A[j + g], A[j + 2g]> をその場でソート
    // すべてのグループの中央値は今や A[p : r] の中央の 3 番目にある
    g^ = g / 3 // 3 要素の副グループの個数
    for j = p to p + g^ - 1     // 副グループをソートする
        <A[j], A[j + g^], A[j + 2g^]> をその場でソートする in place
    // すべての副グループの中央値は、今や A[p : r] の中央の 9 番目にある
    // ピボット x を再帰的に副グループ中央値の中央値として求める
    x = SELECT3(A, p + 4g^, p + 5g^ - 1, ceiling(g^ / 2))
    q = PARTITION-AROUND(A, p, r, x) // ピボットに関して分割
    // 残りは SELECT3 の第19-24行とまったく同じである
    k = q - p + 1
    if i == k
        return A[q] // このピボットの値が答えである
    elseif i < k
        return SELECT3(A, p, q - 1, i)
    else return SELECT3(A, q + 1, r, i - k)

解析

定理 9.3

長さ の入力配列に関する SELECT の実行時間は である。

証明

  1. 概要 手続き SELECT を用いて、長さ の入力配列 に対して i 番目に小さい要素を求める場合を考える。
    このアルゴリズムの実行時間は以下の漸化式で表される：

  2. 漸化式の展開

    • 第 16、23、および 24 行における再帰呼び出しの外側でかかる時間の上界を求める。
    • 第 1-10 行の while ループ は最大 時間で終了する。第 12-13 行で行われる 5 要素グループのソートは、グループ数 に基づき 時間かかる。

  3. 部分問題の削減 ピボット選択後、再帰的な SELECT 呼び出しでは、次のように入力サイズが縮小される：

    • ピボットの両端から除外される要素数の合計は 以上である。

    これをもとに、漸化式 を用いて解析を進める。

  4. 漸化式の解 漸化式を次のように展開する：

結論

以上の解析より、SELECT の実行時間は である。
この結果は SELECT が線形時間で動作することを示している。

≡