C：合併排序具有不規則數量元素的數組

Question

我一直在爲我的作業程序性編程類爲我們提供的合併排序程序不能完全運作。它對具有偶數個整數的數組執行合併排序，但會拋出奇數個整數的分段錯誤。

我理解排序是如何工作的，並且由於奇數導致分段錯誤，因爲數組正在被過度填充。我也明白，解決方案將涉及測試原始數組是否爲偶數，然後根據此值將值傳遞給合併函數。儘管我對程序瞭解得很清楚，但爲了讓這個工作正常進行，我幾個星期來一直把頭靠在牆上，我希望有人能給我一些建議。

在發佈之前，我已經做了很多四處尋找答案，但所有其他示例都涉及合併排序程序和結構，這超出了我迄今爲止學到的內容。你會看到我在下面發佈的代碼。此外，完整的程序還涉及其他一些文件，但我只包含mergesort.c文件和merge.c文件，正如我教授所保證的那樣，文件是唯一需要做出任何更改的地方。 main文件完美工作，只負責填充陣列並調用mergesort函數。如果其他文件是必要的，讓我知道，我會張貼它們。我沒有的唯一原因是因爲我們使用的是Linux shell，而且我還沒有找到將代碼從shell複製並粘貼到我自己的操作系統的實用方法，並且需要一段時間才能寫出來。

在此先感謝您提供的任何指針。這是代碼。

mergesort.c

#include <"mergesort.h"> 

void mergesort(int key[], int n) //key is the array, n is the size of key 
{ 
    int j, k, m, *w; 

    w = calloc(n, sizeof(int)); 
    assert(w != NULL); 

    for (k = 1; k < n; k *= 2) { 
     for (j = 0; j < n - k; j += 2 * k) { 
      merge(key + j, key + j + k, w + j, k, k); 
     } 
     for (j = 0; j < n; ++j) { 
      key[j] = w[j]; 
     } 
    } 
    free(w); 
} 

merge.c

#include "mergesort.h" 

void merge(int a[], int b[], int c[], int m, int n) { 
    int i = 0, j = 0, k = 0; 

    while (i < m && j < n) { 
     if (a[i] < b[j]) { 
      c[k++] = a[i++]; 
     } else { 
      c[k++] = b[j++]; 
     } 
    } 

    while (i < m) { 
     c[k++] = a[i++]; 
    } 
    while (j < n) { 
     c[k++] = b[j++]; 
    } 
} 

Answer 1

您的代碼有一些問題：

• 的包括預處理指令不正確，要麼使用#include "mergesort.h"或#include <mergesort.h>。

• 您必須正確計算傳遞給merge()的數組的大小，以便它不會超出最後一個塊的末尾。按照目前編碼，n必須是2的功率以避免未定義的行爲。

這裏是mergesort.c你的目的修正版本：

#include "mergesort.h" 

void mergesort(int key[], int n) { 
    // key is the array, n is the number of elements 
    int i, j, k, m; 
    int *w; 

    // allocate the working array 
    w = calloc(n, sizeof(int)); 
    // abort the program on allocation failure 
    assert(w != NULL); 

    // for pairs of chunks of increasing sizes 
    for (k = 1; k < n; k *= 2) { 
     // as long as there are enough elements for a pair 
     for (j = 0; j + k < n; j = j + k + m) { 
      // compute the size of the second chunk: default to k 
      m = k; 
      if (j + k + m > n) { 
       // chunk is the last one, size may be smaller than k 
       m = n - j - k; 
      } 
      // merge adjacent chunks into the working array 
      merge(key + j, key + j + k, w + j, k, m); 
      // copy the resulting sorted list back to the key array 
      for (i = 0; i < k + m; i++) { 
       key[j + i] = w[j + i]; 
      } 
     } 
    } 
    free(w); 
} 

以下是有關這個練習一些額外的言論，但你可能不足夠先進和更改API可能是不允許的：

• 使用2個不同的源文件似乎矯枉過正。例程merge是一個輔助功能，值得爲static。它將通過現代編譯器在線擴展。

• 數組大小應該在相應的指針後面（爲了一致性）傳遞爲size_t。

• 而不是斷言分配成功，你應該返回一個失敗代碼，並讓調用者優雅地處理失敗。

• 您可以將工作數組的開始用於所有合併操作。這提高了緩存效率。

這裏是所有這些變化的版本：

static void merge(int a[], size_t m, int b[], size_t n, int c[]) { 
    /* always called with m > 0 and n > 0 */ 
    for (size_t i = 0, j = 0, k = 0;;) { 
     if (a[i] < b[j]) { 
      c[k++] = a[i++]; 
      if (i == m) { 
       while (j < n) { 
        c[k++] = b[j++]; 
       } 
       break; 
      } 
     } else { 
      c[k++] = b[j++]; 
      if (j == n) { 
       while (i < m) { 
        c[k++] = a[i++]; 
       } 
       break; 
      } 
     } 
    } 
} 

：

#include "mergesort.h" 

static void merge(int a[], size_t m, int b[], size_t n, int c[]) { 
    size_t i = 0, j = 0, k = 0; 

    while (i < m && j < n) { 
     if (a[i] < b[j]) { 
      c[k++] = a[i++]; 
     } else { 
      c[k++] = b[j++]; 
     } 
    } 
    while (i < m) { 
     c[k++] = a[i++]; 
    } 
    while (j < n) { 
     c[k++] = b[j++]; 
    } 
} 

int mergesort(int key[], size_t n) { 
    // key is the array, n is the size of key 
    // return 0 for success, -1 for failure with error code in errno 
    size_t i, j, k, m; 
    int *w; 

    w = calloc(n, sizeof(int)); 
    if (w == NULL) 
     return -1; 

    for (k = 1; k < n; k *= 2) { 
     for (j = 0; j + k < n; j += k + m) { 
      m = k; 
      if (j + k + m > n) { 
       m = n - j - k; 
      } 
      merge(key + j, k, key + j + k, m, w + j); 
      // copy the sorted chunk back to the key array 
      for (i = 0; i < k + m; i++) { 
       key[j + i] = w[i]; 
      } 
     } 
    } 
    free(w); 
    return 0; 
} 

您還可以通過在功能merge()除去近一半的指標變量測試提高執行您可以改進mergesort和merge這些更進一步的想法：

• 比較a的最後一個元素和b的第一個元素merge可以在部分或完全排序的陣列上大幅提高速度。

• merge可能會返回要複製的元素數量，刪除排序大小寫中的所有複製。

• 通過將左塊複製到臨時數組併合併到key數組中，可以減小臨時數組的大小。

• 合併均衡塊大小而不是2次冪會減少2個數組大小的非冪次比較的總次數，但使用遞歸方法更容易實現。

Answer 2

所以我發現你的分段錯誤來自哪裏。如果你細看的第一內for循環中的歸併：

 for(j = 0; j < n - k; j += 2 * k) 
     { 
      merge(key + j, key + j + k, w + j, k, k); 
     } 

你會發現，情況並沒有真正與你給什麼合併的功能邊界的切片一致陣列。條件是j < n - k因此最大值j是n - k - 1。但在合併的論點中，您傳遞的第二個數組切片起始於key + j + k，並且您告訴它它的大小爲k，因此如果將j替換爲j的最大值，您將獲得索引j + k + k - 1，您將得到n - k - 1 + k + k - 1 = n。這意味着你正在告訴合併函數他可以去索引n。由於密鑰的大小是n，它沒有索引n。那麼你如何重寫你的狀況呢？我們只計算了合併將訪問的最大索引：j + k + k - 1。所以這意味着你只需要設置j + k + k - 1 < n作爲條件。這意味着：

 for(j = 0; j <= n - (k*2); j += 2 * k) 
     { 
      merge(key + j, key + j + k, w + j, k, k); 
     } 

現在，我們擺脫了段錯誤的，我們可以去到第二部分：使之成爲各種規模的工作。爲什麼它只能用於2的冪（甚至不是所有的均勻尺寸：嘗試對這個[2,3,5,6,4,1]進行排序，你會看到的）是因爲你的k。它設置k決定了將在循環中合併的切片的大小。 k在每輪之後都乘以2，所以它只會得到2的冪的大小！當它不是2的權力時，它會忽略那些「超過」2的權力的部分......如果你明白我的意思，在我們做出改變以解決分割錯誤之前，它只會嘗試去做，但由於這個原因而失敗（並返回一個錯誤）。 我們現在要做的事情是讓它對最後一塊他只是忽略的東西進行排序。因爲這是會改變的唯一的事情，我會只複製歸併功能：

void mergesort(int key[], int n) //key is the array, n is the size of key 
{ 
    int j, k, neglected, *w; 
    w = calloc(n, sizeof(int)); 
    assert(w != NULL); 

    for(k = 1; k < n; k *= 2){ 
     for(j = 0; j <= n - (k*2); j += 2 * k){ 
      merge(key + j, key + j + k, w + j, k, k); 
     } 

     //size of part that got neglected (if it could fully be divided in slices of 2*k, this will be 0) 
     neglected = n % (2*k); 

     //copy everything except the neglected part (if there was none, it will copy everything) 
     for(j = 0; j < n-neglected; ++j) { 
      key[j] = w[j]; 
     } 

     if(neglected != 0 && neglected < n){ //couldn't devide it fully in slices of 2*k ==> the last elements were left out! merge them together with the last merged slice 
      merge(key + n - (2*k) - neglected, key + n-neglected, w + n - (2*k) - neglected, 2*k, neglected); 
      for(j = n - (2*k) - neglected; j < n; ++j) { //copy the part we just merged 
       key[j] = w[j]; 
      } 
     } 

     for(j = 0; j < n; ++j) { 
      key[j] = w[j]; 
     } 
    } 
    free(w); 
} 

而且，我的編譯器抱怨你沒有使用一個變量：m