C：自頂向下合併排序 - 爲什麼無限遞歸？

我想實現合併排序，其中原始和輔助數組爲每次遞歸交替。 It's based on a this Java code。說明如下（Link）：C：自頂向下合併排序 - 爲什麼無限遞歸？

改進。我們可以大幅減少mergesort的運行時間，並仔細考慮對實現的修改。

[...]

消除複製到輔助陣列。可以消除複製到用於合併的輔助數組所需的時間（但不是空間）。爲此，我們使用sort方法的兩個調用，一個從給定數組獲取輸入並將排序後的輸出放入輔助數組中;另一個從輔助數組獲取輸入並將排序後的輸出放入給定數組中。通過這種方法，在一些思維彎曲遞歸技巧中，我們可以安排遞歸調用，以便計算在每個級別切換輸入數組和輔助數組的角色。

以下C代碼是我嘗試交替兩個陣列的作用：

#include <stdlib.h> 
#include <string.h> 

#include "mergesort.h" 

#define THRESHOLD 20 

static size_t size_m = 0; 
static size_t elements = 0; 
static size_t mod = 0; 
static char *a = NULL; 
static char *b = NULL; 
static char *i = NULL; 
static char *j = NULL; 
static char *k = NULL; 
static char *start = NULL; 
static char *middle = NULL; 
static char *end = NULL; 
static char *e = NULL; 
static int (*cmp_m)(const void *, const void *) = NULL; 

void sort(char *a, char *b, size_t lmod, size_t rmod) { 
    elements = rmod-lmod+1; 

    //========== INSERTION SORT ========== 
    if(elements <= THRESHOLD) { 
     start = b+size_m*lmod; 
     end = b+size_m*rmod; 

     for(i = start; i <= end; i += size_m) { 

      memcpy(e, i, size_m); 
      for(j = i-size_m; j >= start && (*cmp_m)((void *)e, (void *)j) < 0; j -= size_m) { 
       memcpy(j+size_m, j, size_m); 
      } 
      memcpy(j+size_m, e, size_m); 
     } 

     return; 
    } 

    //========== SPLIT OPERATION ==========// 
    size_t mmod = (rmod-lmod)/2; 

    sort(b, a, lmod, mmod); 
    sort(b, a, mmod+1, rmod); 

    //========== CHECK IF CURRENT SUBARRAY IS ALREADY SORTED ==========// 
    if((*cmp_m)((void *)(a+size_m*mmod), (void *)(a+size_m*(mmod+1))) <= 0) { 
     memcpy(b+lmod, a+lmod, size_m*elements); 
     return; 
    } 

    //========== MERGE OPERATION ==========// 
    start = a+size_m*lmod; 
    middle = a+size_m*mmod; 
    end = a+size_m*rmod; 

    i = start; 
    j = middle+size_m; 

    for(k = start; k <= end; k += size_m) { 
     mod = k-a; 

     if(i <= middle && (j > end || (*cmp_m)((void *)i, (void *)j) <= 0)) { 
      memcpy(b+mod, i, size_m); 
      i += size_m; 
     } else { 
      memcpy(b+mod, j, size_m); 
      j += size_m; 
     } 
    } 
} 

void mergesort(void *array, size_t num, size_t size, int (*cmp)(const void *a, const void *b)) { 
    size_m = size; 
    threshold = THRESHOLD; 
    a = (char *)array; 
    b = (char *)malloc(num*size_m); 
    e = (char *)malloc(size_m); 
    cmp_m = cmp; 

    memcpy(b, a, size_m*num); 
    sort(b, a, 0, num-1); 

    free(b); 
    free(e); 
}

與Valgrind的仿形後，看來我的代碼不會無限遞歸（該消息是「可以」增長堆棧「）。

爲什麼我的實現做無限遞歸？

來源

2016-09-24 Miroslav Cetojevic

通過一個調試器運行它，它會吐出執行的最後一行。然後嘗試弄清楚爲什麼，如果你不能給我們一個**清晰**，**簡潔**問題描述。 – Downvoter

OT：在C中不要投入'malloc（）'＆Friends。避免全局變量。 – alk

* valgrind *中的堆棧溢出並不一定意味着代碼中有錯誤。如果您的應用程序堆棧很大，很可能是* valgrind *導致了溢出 - 原因是，* valgrind *引入了堆棧變量之間的保護區域，因此可能需要更多的堆棧空間 - 從「ulimit」開始 - 無限「，然後重試你的* valgrind *運行。 – tofro

也許，valgrind無法判斷元素是否遞減。
請嘗試下面的代碼。

static void sort(char *a, char *b, size_t n) { 
     : 
     : 
    //========== SPLIT OPERATION ==========// 

    size_t m = n/2; 
    sort(b, a, m); 
    sort(b + m * size_m, a + m * size_m, n - m);

來源

2016-09-24 15:08:57

C：自頂向下合併排序 - 爲什麼無限遞歸？

回答

相關問題