Heapsort for any type of elements doesn't work

Question

The task was to write heapsort for unknown type of elements in array (using only C code), but my code doesn't work. FOr the following numbers output is '-100 7 -4 0 33 -3 67 1 5 44' I also tried to use the same code for int input only and it worked perfectly. So I think the problem is in changing it to any type of input.

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <memory.h>
typedef int typeEl;
int compare(const void* a, const void* b)
{

    return (*(typeEl*)a - *(typeEl*)b);
}
void swap(void* a, void* b, size_t sizeOfElem) {
    void* tmp = calloc(1,sizeOfElem);
    memcpy(tmp, a, sizeOfElem);
    memcpy(a, b, sizeOfElem);
    memcpy(b, tmp, sizeOfElem);
} 
void heapify (int pos, int n, void* arr, size_t sizeOfElem, int (*comp)(const void* c, const void* d)) { 
    while (2 * pos + 1 < n) {

        int t = 2 * pos +1;
        if (2 * pos + 2 < n && ((char *)arr + (2*pos+2)*sizeOfElem) >= ((char *)arr + t*sizeOfElem))
        {
            t = 2 * pos + 2;
        }
        if (comp((void *) ((char *)arr + pos*sizeOfElem), ((char *)arr + t*sizeOfElem))<0) {
            swap((void *) ((char *)arr + pos*sizeOfElem), (void *) ((char *)arr + t*sizeOfElem), sizeOfElem);
            pos = t;
        } 
        else break;

    }
}

void heap_make(int n, void* arr, size_t sizeOfElem)
{
    for (int i = n - 1; i >= 0; i--)
    {
        heapify(i, n, arr, sizeOfElem, compare );
    }
}

void heap_sort(int n, void* arr, size_t sizeOfElem)
{
    heap_make(n, arr, sizeOfElem);
    while(n>0)
    {
        swap((void *) ((char *)arr), (void *) ((char *)arr + (n-1)*sizeOfElem), sizeOfElem);;
        n--;
        heapify(0,n, arr, sizeOfElem, compare);
    }
}


 int main() {
   int n;
   int m[10] = {1,-3,5,-100,7,33,44,67,-4, 0};

   heap_sort(10, m, sizeof(int));

   for (n=0; n<10; n++)
        printf ("%d ",m[n]);

   return 0;
}

Anyone can advise? Thx for the help!

Answer 1

It can be very hard to decode someone else's code - especially when you are doing all kinds of complicated indexing etc. I had an old copy of a heapify lying around (from an earlier answer - https://stackoverflow.com/a/19749300/1967396 ) and I modified it to work for any type - and to include a full sort.

This doesn't completely answer the question "why is your code not working" - but it does show you some simple techniques you might want to implement as you try to answer the question. Typically, the more readable your code, the easier it is to debug.

Note that, in order to improve readability, I introduced a couple of extra variables (and additional lines of code) - childLeft and childRight are definitely useful; also, you can index elements once you have established a data type for their pointer - since you had a typedef at the start of your code, I simplified some things by doing

typeEl *array;

after which I could index the array with

array[pos];

which is much more readable (and thus less prone to errors) than

*((void *) ((char *)arr + pos*sizeOfElem))

I also defined swap in terms of the array and the indices of the two elements that needed swapping:

void swap(typeEl *arr, int i, int j)

which again makes the code considerably more readable (note also that I don't have to do a calloc).

Anyway - here is the code:

#include <stdio.h>

// define the type of the array that will be sorted:
typedef double typeEl;

void buildHeap(typeEl array[], int n);
void heapify(typeEl array[], int n,  int i);
void heapsort(typeEl array[], int n);
void swap(typeEl array[], int indexA, int indexB);
void printTree(void);

int compare(typeEl a, typeEl b);

typeEl* TREE; // global variable used for printing the entire tree

int main(int argc, char *argv[])
{
typeEl heapArray[] = {1,-3,5,-100,7,33,44,67,-4, 0};
//{0, 1, 2, 3, 4, 5, 6 , 7, 8 ,9 ,10 , 11, 12, 13 ,14 ,15};
int n = sizeof(heapArray)/sizeof(typeEl);
TREE = heapArray;

printf("initial tree:\n");
printTree();
heapsort(heapArray, n);
printf("after heapify\n");
printTree();
printf("as a sorted array:\n");
for(int ii = 0; ii < n; ii++) printf("%d ", (int)heapArray[ii]);
printf("\n");
return 0;
}

void printTree(void)
{
// lazy way to print the entire tree...
  typeEl* array = TREE;
  printf("                        %3d\n ", (int)array[0]);
  printf("            %3d                     %3d\n", (int)array[1], (int)array[2]);
  printf("      %3d         %3d         %3d         %3d\n", (int)array[3], (int)(int)array[4], (int)array[5], (int)array[6]);
  printf("   %3d   %3d   %3d\n", (int)array[7], (int)array[8], (int)array[9]);

  printf("\n");
}

void heapsort(typeEl array[], int n) {
  int i;
  buildHeap(array, n);
  for(i = 1; i < n; i++) {
    buildHeap(array + i, n - i);
  }
}

void buildHeap(typeEl array[], int n)
{
  // change starting condition
  int i = n/2;
  while(i > 0) heapify(array, n,--i);
}

void heapify(typeEl array[], int n,  int i)
{
  // mark nodes initially as -1 to distinguish from "valid" zero
  int childLeft = -1, childRight = -1;
  int largest = i;

  // see if we have valid child nodes:
  if( 2 * i + 1 < n ) childLeft  = 2 * i + 1;
  if( 2 * i + 2 < n ) childRight = 2 * i + 2;

  // see if any nodes are invalid now:
  if(childLeft  < 0 && childRight < 0) return;
  if(childLeft  < 0) childLeft  = childRight;  // can't happen, ever.
  if(childRight < 0) childRight = childLeft; 

  // printf("child left [%i] = %i  child right [%i] = %i\n", childLeft, array[childLeft], childRight, array[childRight]);
  if (compare(array[childLeft], array[i] )) largest = childLeft;
  if (compare(array[childRight] , array[largest])) largest = childRight;
  if(largest != i)
  {
    swap(array, i,largest);
    heapify(array, n, largest);
  }
}

void swap(typeEl array[], int indexA, int indexB)
{
  // printf("swap [%i] %i with [%i] %i\n", indexA, array[indexA], indexB, array[indexB]);
  typeEl temp = array[indexA];
  array[indexA] = array[indexB];
  array[indexB] = temp;
}

int compare(typeEl a, typeEl b) {
  return (a - b>0)?1:0;
}

Sample output:

initial tree:
                          1
              -3                       5
      -100           7          33          44
    67    -4     0

after heapify
                         67
              44                      33
        7           5           1           0
    -3    -4   -100

as a sorted array:
67 44 33 7 5 1 0 -3 -4 -100

As you can see it is sorted high - to - low. Obviously you can change that by simply changing the compare function.