heap sort

[sophia.agnes]

Hi all,

Is there a simple algorithm to implement in heapsort???
this is the program i found in my college D.S notebook
#include<stdio.h>
#include<stdlib.h>

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...???

[Keith Willis]

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

[user923005]

On Nov 13, 6:30 am, [e-mail] 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<stdio.h>
#include<stdlib.h>

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

[pete]

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<stdio.h>
#include<stdlib.h>

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

[Christopher Benson-Manica]

[comp.lang.c] Philip Potter <pg*@see.sig.invalidwrote:

Same again here. Declare 'int a[]' or 'int *a'.

I personally prefer never to use 'type foo[]' - the extra character
really doesn't buy much except some confusion for the unwary.

It looks fine to me. [WRT some heapsort code]

The Java programmer in me (the me that pays the bills these days) says
"Write some unit tests" (to the OP of course).

--
C. Benson Manica | I appreciate all corrections, polite or otherwise.
cbmanica(at)gmail.com |
----------------------| I do not currently read any posts posted through
sdf.lonestar.org | Google groups, due to rampant unchecked spam.

[Szabolcs Nagy]

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?

[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);

--
pete

[Charlie Gordon]

"pete" <pf*****@mindspring.coma écrit dans le message de news:
47***********@mindspring.com...

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.

--
Chqrlie.

[Keith Thompson]

Charlie Gordon wrote:

"pete" <pf*****@mindspring.coma écrit dans le message de news:
47***********@mindspring.com...

>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) <ks***@mib.org>
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"

[Chris Torek]

In article <fi**********@aioe.orgKeith Thompson <ks***@mib.orgwrote:
[much snippage]

>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.

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) [phone]
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.