通用的堆排序：未排序+分段錯誤

Question

我需要建立在C

一個「通用」堆排序我有包括比較功能的主要文件。本質上，數組的基地址，元素數量，每個元素的大小以及比較函數被傳遞到堆排序函數中。我遇到了兩個問題，一個程序沒有對它進行排序，所以我想知道是否有人可以看到代碼有任何問題。兩個1710元素後出現分段錯誤。

#include <stdio.h> 
#include <string.h> 
#include "srt.h" 


void srtheap(void *, size_t, size_t, int (*)(const void *, const void *)); 
void heapify(void *, size_t, size_t, size_t, int (*)(const void *, const void *)); 

void srtheap(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *)) { 
    char *p1, *p2; 
    char *qb=base; 
    void *last = qb + (size*(nelem-1)); 
    for (size_t curpos = nelem-1; curpos>0; curpos=-2){ 
    p1 = qb + ((curpos-1)/2)*size; 
    if(compar(last, (last-size)) >= 0){ 
     if(compar(last, p1) > 0){ 
     swap(last, p1, size); 
     heapify(qb, nelem, curpos, size, compar); 
     } 
    } 
    else { //LEFT>RIGHT 
     if(compar(last-size, p1) > 0){ 
     swap(last-size, p1, size); 
     heapify(qb, nelem, curpos-1, size, compar); 
     } 
      //otherwise, parent is greater than LEFT & RIGHT, 
      //or parent has swapped with child, iteration done, repeat through loop 
    }  //end else, children have been compared to parent 
      //end check for two children, only left child if this loop is skipped 
    last = last-(2*size); 
    } 

/* 
    **Now heapify and sort array 
    */ 
    while(nelem > 0){ 
    last = qb + (size*(nelem-1)); 
    swap(qb, last, size); 
    nelem=nelem-1; 
    heapify(qb, nelem, 0, size, compar); //pass in array, #elements, starting pos, compare 
    } 

} 

void heapify(void *root, size_t numel, size_t pos, size_t sz, int (*compar)(const void *, const void *)){ 
    void *rc, *lc, *p1; 
    while(pos < numel){ 
    rc = root+((pos+1)*2)*sz; //right child 
    lc = root+(((pos+1)*2)-1)*sz; //left child 
    p1 = root+(pos*sz); //parent 
    if((pos+1)*2 < numel){ //check if current element has RIGHT 
     if (compar(rc, lc)>=0){ 
    if(compar(rc, p1)>0) { 
     swap(rc, p1, sz); 
     pos=(pos+1)*2; //move to RIGHT, heapify 
     } 
    else { 
     pos = numel; //PARENT>LEFT&RIGHT, array is heapified for now 
     } 
     } //end RIGHT>LEFT 
     else { //LEFT>RIGHT 
    if(compar(lc, p1) >0) { 
     swap(lc, rc, sz); 
     pos=((pos+1)*2)-1; // move to LEFT, heapify 
    } 
     else { 
     pos = numel; //PARENT>LEFT&RIGHT, array is heapified for now 
     } //end inner if, else 
     }//end LEFT,RIGHT comparison 
    }//end check for RIGHT 
    else if (((pos+1)*2)-1 < numel){ //else, check if element has LEFT 
     if(compar(lc, p1)>0){ 
    swap(lc, p1, sz); 
    pos=((pos+1)*2)-1; //move to LEFT, continue heapify 
     } 
     else { 
    pos = numel; //PARENT>LEFT, array is heapified for now 
     } 
    }//end check for LEFT 
    else { //current element has no children, array is heapified for now 
     pos = numel; 
    } 
    } 
} 

Answer 1

你的代碼和問題似乎驚人地相似this question從2010年，所以我懷疑這是一個家庭作業。

至於崩潰，問題是在這條線在srtheap：

for (size_t curpos = nelem-1; curpos>0; curpos=-2){ 

循環的更新式，curpos=-2是錯誤的。你可能想要curpos-=2。如果是這種情況，仍然存在問題。 size_t是一個無符號類型，所以如果您的原始數組中包含偶數個元素，那麼程序最終將達到curpos等於1的點。當它試圖減去2時，結果將會是一個非常大的正數，而不是您所期望的-1。因此，循環條件curpos>0將評估爲true，並且循環將嘗試訪問遠遠超出數組末尾的數組元素，從而觸發崩潰。

我不願意弄清楚爲什麼你的代碼不能正確排序，因爲它看起來不必要的複雜。這是一個基於this implementation的工作通用堆排序。

void srtheap(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *)) 
{ 
    char *cb = (char *)base; 

    size_t i = (nelem/2); 
    while (1) { 
     heapify(cb, size, i, nelem-1, compar); 
     if (i == 0) break; 
     i--; 
    } 

    for (size_t i = nelem-1; i >= 1; i--) { 
     swap(cb, cb+(size * i), size); 
     heapify(cb, size, 0, i-1, compar); 
    } 
} 

void heapify(char *base, const size_t size, size_t root, const size_t bottom, int (*compar)(const void *, const void *)) 
{ 
    size_t maxChild = root * 2 + 1; 

    if (maxChild < bottom) { 
     size_t otherChild = maxChild + 1; 
     maxChild = (compar(base + (otherChild * size), base + (maxChild * size)) > 0) ? otherChild : maxChild; 
    } else { 
     if (maxChild > bottom) return; 
    } 

    if (compar(base + (root * size), base + (maxChild * size)) >= 0) return; 

    swap(base + (root * size), base + (maxChild * size), size); 

    heapify(base, size, maxChild, bottom, compar); 
} 

該版本使用遞歸，但將其轉換爲循環很容易。我會把它留給讀者。