CODEWITHSUNDEEP
cpointersfunction-pointersvoid-pointersheapsort
user1880760
user1880760

Reputation: 59

Generic heapsort: not sorting + segmentation fault

I need to create a 'generic' heapsort in C.

I have a main file that includes a compare function. Essentially, the base address of the array, number of elements, size of each element, and the compare function are passed into the heapsort functions. I am running into two problems, one the program isn't sorting it so I was wondering if anyone could see anything wrong with the code. Two I am getting a segmentation fault after 1710 elements.

#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;
    }
  }
}

Upvotes: 2

Views: 472

Answers (1)

sjs
sjs

Reputation: 9320

Your code and question seems amazingly similar to this question from 2010, so I suspect this is a homework assignment.

Regarding the crash, the problem is in this line in srtheap:

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

the loop's update expression, curpos=-2 is wrong. You probably want curpos-=2. If that is the case there is still a problem, however. size_t is an unsigned type, so if you have an even number of elements in your original array then eventually the program will reach a point where curpos is equal to 1. When it tries to subtract 2 the result will be a very large positive number, and not -1 as you might be expecting. The loop condition, curpos>0, will therefore evaluate to true, and the loop will try to access an array element far, far beyond the end of the array, triggering a crash.

I'm reluctant to figure out why your code doesn't sort correctly, since it looks needlessly complex. Here's a working generic heapsort based on 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);
}

This version uses recursion, but converting it to a loop is an easy exercise. I'll leave that to the reader.

Upvotes: 2

Related Questions