Generic heapsort

hello, my professor has assigned a generic heapsort in C as a project. I have never programmed in C before and I'm not even sure where to begin. I know that he says that void pointers must be used in order to make it generic. I am only to do the sorting algorithm itself, and I am pretty lost. I don't have much time to complete this, I appreciate any help you guys can give me. He supplied the following code to try to give me an example. I think they're other sorting algorithms.

Code:

---

#ifndef SRT_H
#define SRT_H

#define MAX_BUF 256

void srtbubb(void *, size_t, size_t, int (*)(const void *, const void *));
void srtheap(void *, size_t, size_t, int (*)(const void *, const void *));
void srtquik(void *, size_t, size_t, int (*)(const void *, const void *));
void srtshak(void *, size_t, size_t, int (*)(const void *, const void *));

#endif /* SRT_H */

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include "srt.h"

int intcmp(const void *, const void *);

int main(int argc, char *argv[]) {

  int size = argc == 2 ? atoi(argv[1]) : SHRT_MAX;

  int *a = calloc(size, sizeof(int));

#ifdef RAND
  for (int i = 0; i < size; ++i) {

    a[i] = rand();
  }
#else
  for (int i = 0; i < size; ++i) {

    a[i] = i;
  }
#endif

#if defined BUBB
  srtbubb(a, size, sizeof(int), intcmp);
#elif defined HEAP
  srtinsr(a, size, sizeof(int), intcmp);
#elif defined QUIK
  srtquik(a, size, sizeof(int), intcmp);
#elif defined SHAK
  srtshak(a, size, sizeof(int), intcmp);
#endif

#ifdef PRNT
  for (int i = 0; i < size; ++i) {

    printf("%i\n", a[i]);
  }
#endif

  free(a);

  return 0;
}

int intcmp(const void *p1, const void *p2) {

  if (*(int *)p1 < *(int *)p2) {

    return -5;
  }
  else if (*(int *)p1 > *(int *)p2) {

    return +5;
  }

  return 0;
}

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include "srt.h"

void srtbubb(void *base, size_t nelem, size_t size, int (*cmp)(const void *, const void *)) {

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

    bool sorted = true;

    for (size_t j = 0; j < i; ++j) {

      char *qj = (char *)base + size * j;
      char *qn = qj + size;

      if (cmp(qj, qn) > 0) {

        sorted = false;

        char buf[MAX_BUF];
        char *q1 = qj;
        char *q2 = qn;

        for (size_t m, ms = size; ms > 0; ms -= m, q1 += m, q2 += m) {

          m = ms < sizeof(buf) ? ms : sizeof(buf);

          memcpy(buf, q1, m);
          memcpy(q1, q2, m);
          memcpy(q2, buf, m);
        }
      }
    }

    if (sorted) {

      break;
    }
  }

  return;
}

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

void srtquik(void *base, size_t nelem, size_t size, int (*cmp)(const void *, const void *)) {

  if (nelem > 1) {

    size_t i = 0;
    size_t j = nelem - 1;

    char *qi = (char *)base;
    char *qj = qi + size * j;
    char *qp = qj;

    while (i < j) {

      while (i < j && cmp(qi, qp) <= 0) {

        ++i;
        qi += size;
      }

      while (i < j && cmp(qp, qj) <= 0) {

        --j;
        qj -= size;
      }

      if (i < j) {

        char buf[MAX_BUF];
        char *q1 = qi;
        char *q2 = qj;

        for (size_t m, ms = size; ms > 0; ms -= m, q1 += m, q2 += m) {

          m = ms < sizeof(buf) ? ms : sizeof(buf);

          memcpy(buf, q1, m);
          memcpy(q1, q2, m);
          memcpy(q2, buf, m);
        }

        ++i;
        qi += size;
      }
    }

    if (qi != qp) {

      char buf[MAX_BUF];
      char *q1 = qi;
      char *q2 = qp;

      for (size_t m, ms = size; ms > 0; ms -= m, q1 += m, q2 += m) {

        m = ms < sizeof(buf) ? ms : sizeof(buf);

        memcpy(buf, q1, m);
        memcpy(q1, q2, m);
        memcpy(q2, buf, m);
      }
    }

    ++i;
    qi += size;

    srtquik(base, j, size, cmp);
    srtquik(qi, nelem - i, size, cmp);
  }

  return;
}

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include "srt.h"

void srtshak(void *base, size_t nelem, size_t size, int (*cmp)(const void *, const void *)) {

  for (size_t i = 0, j = nelem - 1; i < j; ++i, --j) {

    bool sorted = true;

    for (size_t k = i; k < j; ++k) {

      char *qk = (char *)base + size * k;
      char *qn = qk + size;

      if (cmp(qk, qn) > 0) {

        sorted = false;

        char buf[MAX_BUF];
        char *q1 = qk;
        char *q2 = qn;

        for (size_t m, ms = size; ms > 0; ms -= m, q1 += m, q2 += m) {

          m = ms < sizeof(buf) ? ms : sizeof(buf);

          memcpy(buf, q1, m);
          memcpy(q1, q2, m);
          memcpy(q2, buf, m);
        }
      }
    }

    if (sorted) {

      break;
    }

    for (size_t k = j - 1; k > i; --k) {

      char *qk = (char *)base + size * k;
      char *qp = qk - size;

      if (cmp(qk, qp) < 0) {

        sorted = false;

        char buf[MAX_BUF];
        char *q1 = qk;
        char *q2 = qp;

        for (size_t m, ms = size; ms > 0; ms -= m, q1 += m, q2 += m) {

          m = ms < sizeof(buf) ? ms : sizeof(buf);

          memcpy(buf, q1, m);
          memcpy(q1, q2, m);
          memcpy(q2, buf, m);
        }
      }
    }

    if (sorted) {

      break;
    }
  }

  return;
}

---

According to the sites Homework policy you will have to either supply some code for your heap-sort, or ask a much more specific question.

--
Mats

Quote:

---

Originally Posted by matsp

According to the sites Homework policy you will have to either supply some code for your heap-sort, or ask a much more specific question.

--
Mats

---

That's the whole problem I'm having. I'm not even sure where to begin exactly. As I said before I've never used C before. The sorting algorithm itself I am pretty familiar with. Perhaps you could just explain to me the parameters for a generic heapsort, including the void pointers. The void pointers I'm a little lost on.

I would expect your generic heapsort function to have a signature similiar to qsort().

The parameters are specified here:

Code:

---

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

---

You use the same parameters for all sort functions, as far as I can tell.

A void pointer is just a "anything pointer", so you can sort any type of object, be it a simple list of characters in an array, or a large struct of personal details [where you perhaps use the lastname + firstname or some identity number (social security/national insurance or such) as the "sort key"].

--
Mats

Thank you for your help. I think I have an idea of what to do now. I've done this in java before, now it's just a matter of figuring out C syntax. I was planning to learn C on my own anyway, but I feel like I'm under the gun now, because it was assigned without even being taught. I appreciate your help and I'll post again if I run into a snag when programming. Also what envirnment do you reccommend for C?

Quote:

---

Originally Posted by Sephiroth1109

Thank you for your help. I think I have an idea of what to do now. I've done this in java before, now it's just a matter of figuring out C syntax. I was planning to learn C on my own anyway, but I feel like I'm under the gun now, because it was assigned without even being taught. I appreciate your help and I'll post again if I run into a snag when programming. Also what envirnment do you reccommend for C?

---

You're quite close to the deeper end of the pool - you may want to study a little bit of simpler code first. Definitely, get yourself a C book of some sort.

--
Mats

Hello everyone, I've been working very hard on this heapsort assignment with my classmates and we've had a lot of difficulties how to keep track of the generic void pointers. I'm going to show you my code below, theoretically it should work because we tried it by hand sorting a tree. But I'm getting a build error. I'm using Deviant C++ which has the ability to compile C files and gcc is in c99 mode otherwise the for loops won't work properly.

Code:

---

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include "srt.h"


#define LEFT(x) ((x<<1) + 1)
#define RIGHT(x) ((x<< 1) +2)
#define PARENT(x) ((x-1) >> 1)

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

void swap(void *p1, void *p2)
{

        char buf[MAX_BUF];
        char *q1 = p1;
        char *q2 = p2;

        for (size_t m, ms = size; ms > 0; ms -= m, q1 += m, q2 += m)
    {

          m = ms < sizeof(buf) ? ms : sizeof(buf);

          memcpy(buf, q1, m);
          memcpy(q1, q2, m);
          memcpy(q2, buf, m);
        }
}

void srtheap(void *base, size_t nelem, size_t size, int (*)(const void *, const void *))
{
    void *p1;
    void *p2;
    void *last = base + (size*(nelem-1));
    int checkchild;
   
   
    size_t index = nelem-1;
   
    for(int i = 0; i< nelem; ++i)
    {
        for(j=0; j< index -1; i++)
        {
                if(RIGHT(index) < nelem)
                {
                        checkchild = 2;
                        p1 = last - size;
                        p2 = last;
                               
                    if(cmp(L,R) > 0)
                    {
                        p2 = base + ((index-j)*size);
                       
                          if(cmp(p1,p2) > 0)
                          {
                              swap(p1,p2);
                                                     
                          }
                      }
                     
                      else if(cmp(p1,p2) < 0)
                      {
                        p1 = base+ ((index-j)*size);

                           
                            if(cmp(p2,p1) > 0)
                            {
                                  swap(p2, p1);
                            }
                      }
                else if(LEFT(index) < nelem)
                {
                  checkchild =1;
                  p1= last;
                  p2 = base+((index-j)*size);
                 
                    if(cmp(p1,p2) > 0)
                    {
                        swap(p1,p2);
                    }             
                }
                --track;
                switch(checkchild)
                {
                  case 1:
                  last = base+(size*index);
                  break;
                  case 2:
                  last = base+size*(index-1);
                  break;
                  default:
                }
                 
            }

   
   
}

---

if you want to be a C89 complient declare the variable at the beginning of the block and not inside the loop.

whether it is c99 or 89 doesn't matter. The supplied code I gave above in my first post was the professors code and his needs c99. Not to mention in class he writes c programs occasionally, but really really basic ones and still uses c99. I just can't figure out why I'm getting a build error.

Where are you getting errors and what errors are you getting? We don't read minds.

What kind of school assigns projects like this without teaching you the basics first? Every school I've ever seen has pre-requisites for all their courses.

well if you really want to know, I attend NJIT. The prerequisites for this course were CS 113 and CS 114. Both were JAVA classes. Our professor likes to give us projects using different languages. This class, CS 280 is called Programming languages and Paradigms, it is mainly a theory class however our professor is a GREAT programmer. The assignments really don't have to do with the contents of the class. I hope that answers anyone's question about that. As for the single error I'm getting, it's a build error. The error is as follows.

Code:

---

# Project: Sort
# Makefile created by Dev-C++ 4.9.8.0

CPP  = g++.exe
CC  = gcc.exe
WINDRES = windres.exe
RES  =
OBJ  = srtshak.o main.o srtbubb.o srtquik.o srtheap.o $(RES)
LINKOBJ  = srtshak.o main.o srtbubb.o srtquik.o srtheap.o $(RES)
LIBS =  -L"C:/Dev-Cpp/lib"
INCS =  -I"C:/Dev-Cpp/include"
CXXINCS =  -I"C:/Dev-Cpp/include/c++"  -I"C:/Dev-Cpp/include/c++/mingw32"  -I"C:/Dev-Cpp/include/c++/backward"  -I"C:/Dev-Cpp/include"
BIN  = Sort.exe
CXXFLAGS = $(CXXINCS)  std=c99
CFLAGS = $(INCS)  std=c99

.PHONY: all all-before all-after clean clean-custom

all: all-before Sort.exe all-after


clean: clean-custom
        rm -f $(OBJ) $(BIN)

$(BIN): $(LINKOBJ)
        $(CC) $(LINKOBJ) -o "Sort.exe" $(LIBS)

srtshak.o: srtshak.c
        $(CC) -c srtshak.c -o srtshak.o $(CFLAGS)

main.o: main.c
        $(CC) -c main.c -o main.o $(CFLAGS)

srtbubb.o: srtbubb.c
        $(CC) -c srtbubb.c -o srtbubb.o $(CFLAGS)

srtquik.o: srtquik.c
        $(CC) -c srtquik.c -o srtquik.o $(CFLAGS)

srtheap.o: srtheap.c
        $(CC) -c srtheap.c -o srtheap.o $(CFLAGS)

---

Yeah I agree with you about the class, but that's why I'm going to transfer out, I feel that the school obviously isn't a place where I can learn. But for now, I'd just like to say thanks for atleast looking at the code I have.

That's no error, that's a makefile.

I'm guessing the error you get is about a symbol cmp undefined? I think this:

Code:

---

void srtheap(void *base, size_t nelem, size_t size, int (*)(const void *, const void *))

---

should be

Code:

---

void srtheap(void *base, size_t nelem, size_t size, int (*cmp)(const void *, const void *))

---

In other words, your sort function needs to know how to compare elements. You also have a cmp(L,R) but I don't see an L or an R anywhere. Your for loop on j increments i. Should you have RIGHT(index) and LEFT(index) or RIGHT(i) and LEFT(i)?

That's what I see right away.


But I'm just guessing, since you are very carefully avoiding telling us anything.

There is no other error then this build error. I just figured since the build error drops it in that make file that there was something there. And I really have told you all that I know, and I've been working on this thing for the duration that it's been assigned. And yeah I just realized I forgot to change my pseudo code back. L and R were used as the Left and Right child. Which later I tried to access as bytes of memory, atleast I think that's what I'm supposed to do. What I'm having trouble with exactly, I need to access the data, maybe cast it to something and have a way to compare it. But I don't know how to do that and keep it generic. If I could maybe store it in an array, but I'm not sure how to do that with data that can be anything. Anywho, there is only 1 error that appears in the list but it doesn't give much information.

C:\Dev-Cpp\Makefile.win [Build Error] [srtshak.o] Error 1

Okay let me try to give in depth what I'm trying to do. I'm trying to do a heapsort which compares the last element first. Checks the children and swaps accordingly. Now what i tried to do is say that base is where the first element is. The last element is the base + (The byte size of the element * the number of elements that there are. I tried to access the data pieces like that, but quite frankly I can't even get my professors sorting algorithms to compile. I tried some different envirnments and actually I feel quite lost. I'm working on this with another classmate right now and what he's trying to do is cast the void pointer into a char. But it doesn't seem to be working for him either. I tried to do several checks inside the loops if it has a child, has a right child if it has a left child, then I tried to swap the datapieces. If this was a constant piece of data, I wouldn't even be asking anything. I tried several times sorting a tree on paper with heapsort, and using these ideas to get to the next data piece, and they all make sense to me. But at this point I don't know whether it's my code that is having a problem or the compiler cannot compile C code. So I'm searching for something, maybe a compiler I can use at the dos prompt. Anywho, thanks again for any suggestions. I'll be continuing to work on this.

Quote:

---

Originally Posted by Sephiroth1109

There is no other error then this build error. I just figured since the build error drops it in that make file that there was something there. And I really have told you all that I know, and I've been working on this thing for the duration that it's been assigned. And yeah I just realized I forgot to change my pseudo code back. L and R were used as the Left and Right child. Which later I tried to access as bytes of memory, atleast I think that's what I'm supposed to do. What I'm having trouble with exactly, I need to access the data, maybe cast it to something and have a way to compare it.

---

You are not supposed to do any such thing. You are not supposed to know anything about this data except (1) its address and (2) the address of a function that compares two pieces of data. Did you see that int (*)(const void *, const void *) in your function declaration? Did you ever wonder what it was? It's a function that will be passed in to your function that knows how to compare ... whatever it is that we have. If your using strings for now, you could pass in strcmp, which does exactly what your code expects of it. You should make the change that I mentioned earlier, and give it a name, like "cmp". (If you want information, you can look up "function pointers in C". In fact, given the name of the class, I would be willing to bet as much as a quarter that the whole point of this assignment was to teach you how to use function pointers.)

Quote:

---

But I don't know how to do that and keep it generic. If I could maybe store it in an array, but I'm not sure how to do that with data that can be anything. Anywho, there is only 1 error that appears in the list but it doesn't give much information.

C:\Dev-Cpp\Makefile.win [Build Error] [srtshak.o] Error 1

---

This tells me that the person who wrote shake sort didn't get theirs done either. You can't compile what you don't have? Anyway, your errors in your file will not be in "Compile Log", but in "Compiler" under Dev-C++. Hit Ctrl-F11 to clear out previous things and re-compile from scratch.

Quote:

---

Okay let me try to give in depth what I'm trying to do. I'm trying to do a heapsort which compares the last element first. Checks the children and swaps accordingly. Now what i tried to do is say that base is where the first element is. The last element is the base + (The byte size of the element * the number of elements that there are. I tried to access the data pieces like that, but quite frankly I can't even get my professors sorting algorithms to compile. I tried some different envirnments and actually I feel quite lost. I'm working on this with another classmate right now and what he's trying to do is cast the void pointer into a char. But it doesn't seem to be working for him either. I tried to do several checks inside the loops if it has a child, has a right child if it has a left child, then I tried to swap the datapieces. If this was a constant piece of data, I wouldn't even be asking anything. I tried several times sorting a tree on paper with heapsort, and using these ideas to get to the next data piece, and they all make sense to me. But at this point I don't know whether it's my code that is having a problem or the compiler cannot compile C code. So I'm searching for something, maybe a compiler I can use at the dos prompt. Anywho, thanks again for any suggestions. I'll be continuing to work on this.

---

Dev-C++ is just gcc, so of course you can use it at a dos prompt if you need to. To get at just your code, you can try "gcc -Wall -c srtheap.c -o srtheap.o" (you may need to put gcc's directory in your path, or type it explicitly; mine is "C:\Dev-Cpp\bin\gcc").

My suggestion, and I'm being serious, is to use real variable names and revise your code. Things look pretty similar to what a heapsort should be, but p1 and p2 don't always seem to mean the same thing and maybe you've got redundant checks, or maybe they're not the same check but you're reusing the names, or something. As to compiling, if you don't have all 5 .c files in hand ready to go, the build will never work. Maybe remove all but yours (and main--was that instructor written or you written?) so that you don't have to worry about the other three.