443,719 Members | 1,875 Online
Need help? Post your question and get tips & solutions from a community of 443,719 IT Pros & Developers. It's quick & easy.

heap sort

 P: n/a Hi all, Is there a simple algorithm to implement in heapsort??? this is the program i found in my college D.S notebook #include #include void heapsort (int[], int); void siftdown (int[], int, int); int main (void) { int a[5] = { 44, 22, 66, 77, 11 }; int i; puts ("\n Before Sorting:: "); for (i = 0; i < 5; i++) printf ("%d\t", a[i]); heapsort (a, 5); puts ("\n After Sorting:: "); for (i = 0; i < 5; i++) printf ("%d\t", a[i]); puts (""); return (EXIT_SUCCESS); } void heapsort (int a[5], int size) { int i, temp; /* * heap creation */ for (i = size / 2; i >= 0; i--) { siftdown (a, i, size - 1); } for (i = (size - 1); i >= 1; i--) { temp = a[0]; a[0] = a[i]; a[i] = temp; siftdown (a, 0, i - 1); } /*finding the max element & putting in last pos */ } void siftdown (int a[5], int r, int b) { int done, maxchild, temp; done = 0; while ((r * 2 <= b) && (!done)) { if (r * 2 == b) maxchild = r * 2; else if (a[r * 2] a[r * 2 + 1]) maxchild = r * 2; else maxchild = r * 2 + 1; /*check if root element < max child element,if it so swap, * set root pos = max child pos * */ if (a[r] < a[maxchild]) { temp = a[r]; a[r] = a[maxchild]; a[maxchild] = temp; r = maxchild; } else done = 1; } } how good is this program??? is there a better/simpler algorithm to create heap than which is used here...??? Nov 13 '07 #1
9 Replies

 P: n/a On Tue, 13 Nov 2007 14:30:03 -0000, so**********@gmail.com wrote: >Is there a simple algorithm to implement in heapsort???this is the program i found in my college D.S notebook http://en.wikipedia.org/wiki/Sorting_algorithm (particularly http://en.wikipedia.org/wiki/Sorting...ing_algorithms) then http://en.wikipedia.org/wiki/Heapsort -- PGP key ID 0xEB7180EC Nov 13 '07 #2

 P: n/a On Nov 13, 6:30 am, sophia.ag...@gmail.com wrote: Hi all, Is there a simple algorithm to implement in heapsort??? this is the program i found in my college D.S notebook #include #include void heapsort (int[], int); void siftdown (int[], int, int); int main (void) { int a[5] = { 44, 22, 66, 77, 11 }; int i; puts ("\n Before Sorting:: "); for (i = 0; i < 5; i++) printf ("%d\t", a[i]); heapsort (a, 5); puts ("\n After Sorting:: "); for (i = 0; i < 5; i++) printf ("%d\t", a[i]); puts (""); return (EXIT_SUCCESS); } void heapsort (int a[5], int size) { int i, temp; /* * heap creation */ for (i = size / 2; i >= 0; i--) { siftdown (a, i, size - 1); } for (i = (size - 1); i >= 1; i--) { temp = a[0]; a[0] = a[i]; a[i] = temp; siftdown (a, 0, i - 1); } /*finding the max element & putting in last pos */ } void siftdown (int a[5], int r, int b) { int done, maxchild, temp; done = 0; while ((r * 2 <= b) && (!done)) { if (r * 2 == b) maxchild = r * 2; else if (a[r * 2] a[r * 2 + 1]) maxchild = r * 2; else maxchild = r * 2 + 1; /*check if root element < max child element,if it so swap, * set root pos = max child pos * */ if (a[r] < a[maxchild]) { temp = a[r]; a[r] = a[maxchild]; a[maxchild] = temp; r = maxchild; } else done = 1; } } how good is this program??? is there a better/simpler algorithm to create heap than which is used here...??? Your post is topical in news:comp.programming -- which talks about various aspects of programming including algorithms. That code looks like it came from here: http://linux.wku.edu/~lamonml/algor/sort/heap.html and specifically: http://linux.wku.edu/~lamonml/algor/sort/heap.c but the code on the web site is a bit better than the book's. I hope the book gave credit. The sort looks well executed to me, but I have not bothered to test or benchmark it. Generally speaking, heapsort is used as a "last resort" in the introspective sort algorithm. Follow-up set to news:comp.programming Nov 13 '07 #3

 P: n/a so**********@gmail.com wrote: > Hi all, Is there a simple algorithm to implement in heapsort??? this is the program i found in my college D.S notebook #include #include void heapsort (int[], int); void siftdown (int[], int, int); int main (void) { int a[5] = { 44, 22, 66, 77, 11 }; int i; puts ("\n Before Sorting:: "); for (i = 0; i < 5; i++) printf ("%d\t", a[i]); heapsort (a, 5); puts ("\n After Sorting:: "); for (i = 0; i < 5; i++) printf ("%d\t", a[i]); puts (""); return (EXIT_SUCCESS); } void heapsort (int a[5], int size) { int i, temp; /* * heap creation */ for (i = size / 2; i >= 0; i--) { siftdown (a, i, size - 1); } for (i = (size - 1); i >= 1; i--) { temp = a[0]; a[0] = a[i]; a[i] = temp; siftdown (a, 0, i - 1); } /*finding the max element & putting in last pos */ } void siftdown (int a[5], int r, int b) { int done, maxchild, temp; done = 0; while ((r * 2 <= b) && (!done)) { if (r * 2 == b) maxchild = r * 2; else if (a[r * 2] a[r * 2 + 1]) maxchild = r * 2; else maxchild = r * 2 + 1; /*check if root element < max child element,if it so swap, * set root pos = max child pos * */ if (a[r] < a[maxchild]) { temp = a[r]; a[r] = a[maxchild]; a[maxchild] = temp; r = maxchild; } else done = 1; } } how good is this program??? is there a better/simpler algorithm to create heap than which is used here...??? These functions: void hsortm(e_type *array, size_t nmemb); void hsortx1(e_type *array, size_t nmemb); void heapSort2(e_type *array, size_t nmemb); void heapSort2p1(e_type *array, size_t nmemb); void husort(e_type *array, size_t nmemb); void husort2(e_type *array, size_t nmemb); void hesort(e_type *array, size_t nmemb); at http://www.mindspring.com/~pfilandr/C/e_driver/e_sort.c are different implementations of heapsort. I don't think that any one of them is simpler than what you've posted. -- pete Nov 14 '07 #4

 P: n/a [comp.lang.c] Philip Potter

 P: n/a pete wrote: I use lower case for the str() and xstr() macros, because I also copy them out of the standard that way. str() macro in the standard? you mean the dummy example for macro usage (6.10.3.5)? is it useful? Nov 15 '07 #6

 P: n/a Szabolcs Nagy wrote: > pete wrote: I use lower case for the str() and xstr() macros, because I also copy them out of the standard that way. str() macro in the standard? you mean the dummy example for macro usage (6.10.3.5)? Yes. is it useful? It can be. #define LENGTH 40 #define str(x) # x #define xstr(x) str(x) char array[LENGTH + 1]; int rc = fscanf(stdin, "%" xstr(LENGTH) "[^\n]%*[^\n]", array); -- pete Nov 15 '07 #7

 P: n/a "pete" >pete wrote: I use lower case for the str() and xstr() macros, because I also copy them out of the standard that way. str() macro in the standard?you mean the dummy example for macro usage (6.10.3.5)? Yes. >is it useful? It can be. #define LENGTH 40 #define str(x) # x #define xstr(x) str(x) char array[LENGTH + 1]; int rc = fscanf(stdin, "%" xstr(LENGTH) "[^\n]%*[^\n]", array); Thanks for pointing out how limited fscanf is. Improvements are badly needed such as the ability to pass dynamic sizes for destination arrays. The macro trick above is a limited solution, contorted, partial and fragile: a good example of stringization, but also a good example of cryptic code to be avoided. -- Chqrlie. Nov 25 '07 #8

 P: n/a Charlie Gordon wrote: "pete" Szabolcs Nagy wrote: >>pete wrote:I use lower case for the str() and xstr() macros,because I also copy them out of the standard that way.str() macro in the standard?you mean the dummy example for macro usage (6.10.3.5)? Yes. >>is it useful? It can be.#define LENGTH 40#define str(x) # x#define xstr(x) str(x)char array[LENGTH + 1];int rc = fscanf(stdin, "%" xstr(LENGTH) "[^\n]%*[^\n]", array); Thanks for pointing out how limited fscanf is. Improvements are badly needed such as the ability to pass dynamic sizes for destination arrays. The macro trick above is a limited solution, contorted, partial and fragile: a good example of stringization, but also a good example of cryptic code to be avoided. Interesting. A couple of observations. First, this particular method can be used only if you have the length as a literal decimal integer constant. Stringizing something like ``sizeof(buf)'' won't do you much good here. A more general solution is to use sprintf() or snprintf() to build the format string; this requires no precessor tricks, but it imposes some runtime overhead, and determining the required length for the format string can be tricky. Second, fprintf allows a precision or length modifier to be specified with an asterisk '*', which causes the value to be read from an int argument. I wonder why fscanf doesn't have this facility. fscanf uses '*' to denote assignment suppression, but surely an alternative syntax could have been invented. -- Keith Thompson (The_Other_Keith) Looking for software development work in the San Diego area. "We must do something. This is something. Therefore, we must do this." -- Antony Jay and Jonathan Lynn, "Yes Minister" Nov 27 '07 #9

 P: n/a In article Second, fprintf allows a precision or length modifier to be specifiedwith an asterisk '*', which causes the value to be read from an intargument. I wonder why fscanf doesn't have this facility. fscanf uses'*' to denote assignment suppression, but surely an alternative syntaxcould have been invented. Indeed -- yet I would suggest that adding indirect field widths to scanf is a little like adding a coffee-pot heater to a chainsaw that has no off-switch ("this thing wastes power, we could use it to heat our coffee when we're not cutting trees"). Sure, it would work fine, but it would be better to use a device with safer modes of operation (i.e., to replace the scanf family with something that "works right" :-) ). -- In-Real-Life: Chris Torek, Wind River Systems Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603 email: forget about it http://web.torek.net/torek/index.html Reading email is like searching for food in the garbage, thanks to spammers. Nov 30 '07 #10