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

分析

マージソートの実行時間を次のように考えてみましょう。 T(n)。したがって、

$ T(n)= \ begin {cases} c&if \:n \ leqslant 1 \\ 2 \:x \:T(\ frac {n} {2})+ d \:x \:n&else \ end {cases} $ここで、cdは定数です

したがって、この漸化式を使用すると、

$$ T(n)= 2 ^ i T(\ frac {n} {2 ^ i})+ idn $$

として、$ i = log \:n、\:T(n)= 2 ^ {log \:n} T(\ frac {n} {2 ^ {log \:n}})+ log \:ndn $

$ = \:cn + dnlog \:n $

したがって、$ T(n)= O(n \:log \:n)$

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