heap sort

This is a discussion on heap sort within the C Programming forums, part of the General Programming Boards category; I am trying to write a heap sort function using the prototype: Code: void heap_sort(void *base, size_t nel, size_t width, ...

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    19

    heap sort

    I am trying to write a heap sort function using the prototype:

    Code:
    void
    heap_sort(void *base, size_t nel, size_t width, int(*compar)(const void *, const void *));
    where base is a pointer to the first element
    nel is the number of elements to be sorted
    width is the size of each element
    and compar is a standard comparison function

    (the same prototype for the library function qsort)
    I have successfully written a swap_data function and the necessary comparison functions.

    I was wondering if anyone can give me some hints on how to do things like setting child = 2 * parent + 1 using these definitions when parent and child are void* items. I keep getting "assignment makes pointer from integer without a cast" and "invalid use of unary *" errors.

    Thanks

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    I posted a generic quicksort implementation a while back. The quality is debatable (written in a hurry), but it should give you some ideas on how to do your heapsort implementation.
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Apr 2005
    Posts
    19
    Thanks, that cleared up some things, but I still cannot find the child nodes. The children appear at 2*parent+1 in a heap as far as I know, but when parent is void* (or unsigned char*) rather than being an int in an array, I just don't know how to find the child.

  4. #4
    Registered User
    Join Date
    Apr 2005
    Posts
    19
    Don't worry, I worked everything out, yay!

    For anyone that was interested, instead of doing:

    Code:
    child = 2*parent + width
    I just did:

    Code:
    child = parent + (parent - base) + width
    which makes sense if you think about it long enough, and draw diagrams and stuff
    Last edited by lucaspewkas; 04-30-2005 at 05:24 AM.

  5. #5
    Registered User
    Join Date
    Apr 2004
    Posts
    173
    Out of curiousity, do you go to Melb Uni?
    Well because we nearly got the same question and at the same time for 1 of our assignments.
    The cost of software maintenance increases with the square of the programmer's creativity.

  6. #6
    Registered User
    Join Date
    Apr 2005
    Posts
    19
    Yep, pretty easy to guess I suppose, damn sorting project took me ages. Still, I learned a hell of a lot from it so it's not all bad.

  7. #7
    Registered User
    Join Date
    Apr 2004
    Posts
    173
    Haha yer the report was a pain to write
    The cost of software maintenance increases with the square of the programmer's creativity.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. heap sort problem
    By Cpro in forum C++ Programming
    Replies: 2
    Last Post: 02-04-2008, 04:54 AM
  2. How do I heap sort alphabetically?
    By arih56 in forum C++ Programming
    Replies: 7
    Last Post: 12-12-2007, 01:00 AM
  3. Heap Sort
    By silicon in forum C++ Programming
    Replies: 1
    Last Post: 05-18-2005, 01:53 PM
  4. heap question
    By mackol in forum C Programming
    Replies: 1
    Last Post: 11-30-2002, 05:03 AM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21