Design-and-analysis-of-algorithms-merge-sort

DAA-ソートのマージ

この章では、マージソートについて説明し、その複雑さを分析します。

問題文

数のリストをソートする問題は、すぐに分割統治戦略に役立ちます。リストを2つの半分に分割し、各半分を再帰的にソートしてから、ソートされた2つのサブリストをマージします。

溶液

このアルゴリズムでは、数値は配列 numbers [] _ に格納されます。 ここで、 ' p_' および q はサブ配列の開始インデックスと終了インデックスを表します。

Algorithm: Merge-Sort (numbers[], p, r)
if p < r then
q = ⌊(p + r)/2⌋
Merge-Sort (numbers[], p, q)
    Merge-Sort (numbers[], q + 1, r)
    Merge (numbers[], p, q, r)

Function: Merge (numbers[], p, q, r)
n1 = q – p + 1
n2 = r – q
declare leftnums[1…n1 + 1] and rightnums[1…n2 + 1] temporary arrays
for i = 1 to n1
   leftnums[i] = numbers[p + i - 1]
for j = 1 to n2
   rightnums[j] = numbers[q+ j]
leftnums[n1 + 1] = ∞
rightnums[n2 + 1] = ∞
i = 1
j = 1
for k = p to r
   if leftnums[i] ≤ rightnums[j]
      numbers[k] = leftnums[i]
      i = i + 1
   else
      numbers[k] = rightnums[j]
      j = j + 1

分析

Merge-Sortの実行時間を T（n） として考えてみましょう。 したがって、

$ T（n）= \ begin \ {cases} c＆if \：n \ leqslant 1 \\ 2 \：x \：T（\ frac \ {n} \ {2}）+ d \：x \：n ＆それ以外の場合\ end \ {cases} $ここで、_c_および_d_は定数です

したがって、この再帰関係を使用して、

T（n）= 2 ^ i T（\ frac \ {n} \ {2 ^ i}）+ i.d.n

As、$ i = log \：n、\：T（n）= 2 ^ \ {log \：n} T（\ frac \ {n} \ {2 ^ \ {log \：n}}）+ log \ ：ndn $

$ = \：c.n + d.n.log \：n $

したがって、$ T（n）= O（n \：log \：n）$

例

次の例では、Merge-Sortアルゴリズムを段階的に示しています。 最初に、サブ配列に要素が1つだけ含まれるまで、すべての反復配列が2つのサブ配列に分割されます。 これらのサブアレイをさらに分割できない場合、マージ操作が実行されます。

例