2015-02-06 98 views
2

我想知道這個遞歸算法的流程是如何工作的:an inversion counter based on merge-sort。當我查看merge-sort遞歸樹的圖時,它看起來相當清晰;我認爲葉子會一直分裂,直到每片葉子是一個單元,然後merge()將開始合併它們;因此,開始「移回」樹 - 可以這麼說。瞭解mergesort-like算法中的遞歸

但在下面的代碼,如果我們打印出此功能與給定數組print(sortAndCount(test_case))那麼我們實際上得到來自merge()功能,而不是在sortAndCount() return語句我們的「最終」輸出?所以在下面的代碼中,我認爲sortAndCount()方法會在(invCountA, A) = sortAndCount(anArray[:halfN])中反覆調用它自己,直到達到基本情況,然後繼續處理數組的下一半 - 但現在看起來不正確。有人能糾正我對這種遞歸流的理解嗎? (鈮我截斷部分代碼爲merge()方法,因爲我只關心的遞歸過程。)

def sortAndCount(anArray): 
    N = len(anArray) 
    halfN = N // 2 

    #base case: 
    if N == 1: return (0, anArray)   

    (invCountA, A) = sortAndCount(anArray[:halfN]) 
    (invCountB, B) = sortAndCount(anArray[halfN:]) 
    (invCountCross, anArray) = merge(A, B) 

    return (invCountA + invCountB + invCountCross, anArray) 

def merge(listA, listB): 
    counter = 0 
    i, j = 0, 0 

    #some additional code... 
    #... 
    #... 


    #If all items in one array have been selected, 
    #we just return remaining values from other array: 
    if (i == Asize):         
     return (counter, output_array + listB[j:]) 
    else: 
     return (counter, output_array + listA[i:]) 
+0

邏輯與mergesort相同,唯一的區別是我們通過計算剩餘在左側的項目來計算分割反轉,當我們找到右側較小的元素時。 – 2015-02-06 17:51:31

+0

你問關於拆分倒置或mergesort? – 2015-02-06 18:27:15

+0

嗯,我正在問這個[split-inversions],但正如你所說,它與mergesort非常相似。我的問題是我試圖展開遞歸調用。關鍵是我不知道在行'(invCountA,A)= sortAndCount(anArray [:halfN])''上發生了什麼。解釋器在繼續之前是否停止計算遞歸的每個級別 - 即它是否通過'(invCountA,A)= sortAndCount(anArray [:halfN])完成遞歸,直到它達到N大小1,還是創建佔位符,同時繼續通過代碼(只有然後通過遞歸的每個級別)? – Eyeofpie 2015-02-06 19:19:37

回答

2

以下圖像創建使用rcviz示出了遞歸調用的順序,作爲文檔中說明邊按照執行遍歷的順序進行編號。邊的顏色從黑到灰表示遍歷順序:先黑邊,後邊是灰邊。

enter image description here

因此,如果我們遵循的步驟緊密我們可以看到,我們首先遍歷原始數組的左半部分則完全正確的。