Thread: Heapsort

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    1

    Heapsort

    How would I code Heapsort using this code? Can someone please help.
    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 */
    
    /*
     *
     *  main.c file
     *
     */
    
    #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
      srtheap(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]);
      }
    #else
      for (int i = 0; i < size - 1; ++i) {
        if (a[i] > a[i + 1]) {
          printf("Fail\n");
          goto exit;
        }
      }
    
      printf("Pass\n");
    #endif
    
    exit:
    
      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;
    }
    
    /*
     *
     *  srtbubb.c file
     *
     */
    
    #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;
    }
    
    /*
     *
     *  srtquik.c file
     *
     */
    
    #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;
    }
    
    /*
     *
     *  srtshak.c file
     *
     */
    
    #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;
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Do you know what heapsort looks like as an algorithm?

  3. #3
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    first, im not even looking at the code.

    do you not understand the code? is it even yours? if this is homework and your supposed to do it yourself, did you write the above code?

    ask a specific question regarding a specific portion/function of your code. look around, say wikipedia, for the heapsort algorithm with pseudocode--or whatever language you need it in, you will be able to find it with explanation.

    no one is going to say 'oh, here is your complete answer with no effort on your part.' tell us what you need help with, exactly.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Heapsort
    By myle in forum C++ Programming
    Replies: 5
    Last Post: 06-26-2008, 01:44 AM
  2. heapsort help please!
    By MAC77 in forum C++ Programming
    Replies: 2
    Last Post: 12-14-2005, 12:28 PM
  3. Heapsort
    By abalfazl in forum C Programming
    Replies: 2
    Last Post: 08-06-2005, 06:11 PM
  4. heapsort problem...
    By talz13 in forum C++ Programming
    Replies: 9
    Last Post: 09-23-2003, 04:06 PM
  5. heapsort help plz
    By nsssn73 in forum C# Programming
    Replies: 0
    Last Post: 06-02-2002, 06:54 AM