マージソートトレースの明確化

Question

マージソートのプロセスをトレースするのが少し難しいです... 概念的には、ソートされていない配列は、サブ配列のサブ配列が長さ1これはソートされていると言われる各要素を1つずつ含む配列になります。 言うのソートされていないアレイ上

mergeSort(A,p,r) //where p = lowest index, r = highest 
    if (p < r) { 
     q = (p+r)/2 
     mergeSort(A,p,q) 
     mergeSort(A,q+1,r) 
     merge(A,p,q,r) 
    } 

を用いて[3、5、2、1、6、4] pは素子3におけるインデックスであり、qは素子2のインデックスとRでインデックスされています私の理解から、 は、mergeSort（A、p、q）を呼び出すために、最初に[3,5,2]に分割されます。新しいインデックスは要素3でq、要素5でq、要素2でrになります。したがって、[3,5,2]は、pを用いて[3,5]に分割され、qは要素3のインデックスであり、rは要素5のインデックスである。これは[3]に分割される。私の質問は、[2]（除算後の[3,5,2]から）はpまたはq + 1として索引付けされていますか？

....実際には、[3,5,2,1,6,4]が[3、5、2、1、6、4]に分割されるので、別の方法で質問すると、 5,2]および[1,6,4]である。 [3,5]と[2]に分けられる。 [1,6]および[4]。これは[3] [5] [1] [6]にも分けられる。どの部門のどの部分がmergeSort（A、p、q）を呼び出し、部門のどの部分がmergeSort（A、q + 1、r）を呼び出すか？ [1、6、4]も要素1でp、要素4でr、

Answer 1

これを追跡する最も簡単な方法は、鉛筆と紙を使うことです。そしてそれはあなたのためにやってください。

従うべき規則はありますか？はい、関数を呼び出すと、その関数が実行されます。 （またはあなたの注意がその機能にあるべきです）。私は何を意味

は次のとおりです。 -

mergesort([3, 5, 2, 1, 6, 4])あなたが呼ばれます。

は、その後、最終的に、あなたは今、あなたの注意が mergesort([3,5,2])

にあなたが上に行くだろう、この方法でなければなりません。このライン

 q = (p+r)/2 
    mergeSort(A,p,q) [3,5,2] <------ 
    mergeSort(A,q+1,r) [1,6,4] 
    merge(A,p,q,r) 

に直面しています。そして、ある時点であなたはこの行に到達します。

 q = (p+r)/2 
    mergeSort(A,p,q) [2,3,5] // this is sorted now 
    mergeSort(A,q+1,r) [1,6,4] <-------- 
    merge(A,p,q,r) 

このようにしてください。この方法で、ある時点で、mergeが呼び出され、ソートされたサブアレイがソートされた完全な配列にマージされます。

• mergeSort(A,p,q)をソートするときは、自分自身を悩まさないでください。mergeSort(A,q+1,r)この部分配列がソートされない限り、他の部分は呼び出されません。私はあなたに別の画像を表示してみましょうあなたの2番目の質問への答えとして

---

。

[3, 5, 2, 1, 6, 4] 
    p  q  r 
     /\ 
[3,5,2] [1, 6, 4] 
p q r p q r 
    | \  | \ 
[3,5] [2] [1, 6] [4] 
p r  p r 
q   q 
/\  |\ 
[3] [5]  [1] [6] 

これは、アレイ上でmergesortが呼び出される方法です。

リコースでは、すべての関数呼び出しには独自のパラメータがあります。子配列の親配列でqとして機能するものは、pまたはrとなります。