Thread: Generic heapsort

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    14

    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;
    }
    Last edited by Sephiroth1109; 11-29-2007 at 08:01 AM.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Nov 2007
    Posts
    14
    Quote Originally Posted by matsp View Post
    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.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I would expect your generic heapsort function to have a signature similiar to qsort().
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Registered User
    Join Date
    Nov 2007
    Posts
    14
    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?

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Sephiroth1109 View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Registered User
    Join Date
    Nov 2007
    Posts
    14
    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:
                    }
                       
                }
    
        
        
    }
    Last edited by Sephiroth1109; 12-07-2007 at 01:32 PM.

  9. #9
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    if you want to be a C89 complient declare the variable at the beginning of the block and not inside the loop.
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  10. #10
    Registered User
    Join Date
    Nov 2007
    Posts
    14
    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.

  11. #11
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Where are you getting errors and what errors are you getting? We don't read minds.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #12
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    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.

  13. #13
    Registered User
    Join Date
    Nov 2007
    Posts
    14
    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.

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  15. #15
    Registered User
    Join Date
    Nov 2007
    Posts
    14
    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.
    Last edited by Sephiroth1109; 12-07-2007 at 05:43 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Generic function
    By vin_pll in forum C++ Programming
    Replies: 26
    Last Post: 02-04-2009, 07:36 AM
  2. generic printing preferences dialog box
    By stanlvw in forum Windows Programming
    Replies: 8
    Last Post: 06-27-2008, 02:20 AM
  3. heapsort help please!
    By MAC77 in forum C++ Programming
    Replies: 2
    Last Post: 12-14-2005, 12:28 PM
  4. Generic Host Proccess Shutdown
    By Tommaso in forum Tech Board
    Replies: 8
    Last Post: 08-14-2003, 11:18 AM
  5. Generic Progpammimg Iterators
    By rip1968 in forum C++ Programming
    Replies: 7
    Last Post: 08-06-2002, 10:20 AM