Mergesort互換和比較

我目前正在研究一個分析項目，我正在觀察在Java中實現時不同算法的行爲。我得到了一些代碼，它實現了在線的Mergesort算法，現在我需要在10,000個隨機生成的整數（1到100,000）的數組上運行這個代碼並記錄進行了多少次交換和比較。Mergesort互換和比較

我不太確定代碼中的哪一點增加計數交換和比較的變量。預期的價值是多少？因爲Mergesort的最好，最差和平均情況都是nlog（n），這是否意味着我應該期望10,000 *（10,000的基數爲2）約爲138,000，用於交換和比較的總和？

下面是代碼，我猜，當原始數組改變的交換隻發生，比較我不太確定：

void MergeSort(int low, int high) 
    // a[low : high] is a global array to be sorted. 
// Small(P) is true if there is only one element to 
// sort. In this case the list is already sorted. 
{ 
    if (low < high) { // If there are more than one element 
      // Divide P into subproblems. 
      // Find where to split the set. 
      int mid = (low + high)/2; 
      // Solve the subproblems. 
      MergeSort(low, mid); 
      MergeSort(mid + 1, high); 
      // Combine the solutions. 
      Merge(low, mid, high); 
    } 
} 

    void Merge(int low, int mid, int high) 
// a[low:high] is a global array containing two sorted 
// subsets in a[low:mid] and in a[mid+1:high]. The goal 
// is to merge these two sets into a single set residing 
// in a[low:high]. b[] is an auxiliary global array. 
{ 
    int h = low, i = low, j = mid+1, k; 
    while ((h <= mid) && (j <= high)) { 
     if (a[h] <= a[j]) { b[i] = a[h]; h++; } 
     else { b[i] = a[j]; j++; } i++; 
    } 
    if (h > mid) for (k=j; k<=high; k++) { 
        b[i] = a[k]; i++; 
       } 
    else for (k=h; k<=mid; k++) { 
      b[i] = a[k]; i++; 
     } 
    for (k=low; k<=high; k++) a[k] = b[k];

}

來源

2012-07-29 Mike

您好！每個if（）語句都是比較的，如果你說b [i] = a [k]，它就是交換。你需要數，這些操作執行多少次。 – 2012-07-29 21:31:52

while或for循環中的操作是否也算作比較？例如，如果你有（while）（i 0），那麼它每次循環時都會作爲比較計數嗎？事實上，它是否被視爲兩個比較，因爲如果第一個不是錯誤的，你可能需要對它們進行評估？ – Mike 2012-07-29 22:11:42

我不確定代碼中的哪一點會增加計數交換和比較的變量。

我建議你創建的helper方法用於交換和比較操作。這會給你增量計數器代碼的好地方。

因爲最好，最差，平均歸併情況下都是n日誌（N），這是不是意味着我應該期待萬掉期和比較的總和（日誌的10,000個鹼基2）約= 138000？ *

你能想到的是，比較的次數成正比的n log（n）的當輸入的大小是ñ。

來源

2012-07-29 21:08:52 aioobe

沒有明確的交換和比較操作，我不知道如何實現幫助器方法。您提出的關於比例的第二點是我不知道的。這是什麼意思？比例可以是主觀的，在某些常數上是成比例的？迄今爲止，我的結果是，互換保持穩定的133616點數，比較變化在130463點左右。這大約與原始複雜度成比例2nlog（n）。 – Mike 2012-07-29 21:15:13

'boolean compare（int a，int b）{compareCount ++;返回一個 aioobe 2012-07-29 21:16:54

我實際上是在算法和數據結構中做家庭作業。線程是有點塵土飛揚，但任何人誰可以使用它，這是我得到了什麼：

在您的合併方法

while ((h <= mid) && (j <= high)) { 
    if (a[h] <= a[j]) { b[i] = a[h]; h++; } 
    else { b[i] = a[j]; j++; } i++; 
}

if語句是比較正取得在哪裏，我幾乎要說即使你對else語句進行了比較，也由於if語句失敗了。

else語句是開始交換的地方，如果您在else語句中放置一個計數器，它將計算所有交換。我通過檢查數組兩次來確認這一點，一次未排序時再次排序。我不是100％，所以任何反饋意見。這是一個小更容易在我的任務看，因爲我字符串進行排序，這些都是在你的合併功能相同的路線貼上面，從我的任務：

while(leftPos<=leftEnd && rightPos<=rightEnd) 
{ 
    mergeSortComparisons++; 

    if (a[leftPos].compareTo(a[rightPos]) <= 0)  
     tmpArray[tmpPos++]=a[leftPos++]; 

    else 
    { 
     tmpArray[tmpPos++]=a[rightPos++]; 
     mergeSortSwaps++; 
    } 
}

mergeSortSwaps和mergeSortComparisons是在設定的類變量構造函數。如果我記得該方法，我可以重置它們。

來源

2012-11-07 02:32:09 Xav

在您的合併功能，我添加了一個變盤點這將有總交換數目進行

while ((h <= mid) && (j <= high)) { 
     if (a[h] <= a[j]) { b[i] = a[h]; h++; } 
     else { b[i] = a[j]; j++; count+=mid-h+1; } i++; 
    }

來源

2013-08-02 23:03:37 Osama

Mergesort互換和比較

回答

相關問題