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

heapsort (a, 5);

puts ("\n After Sorting:: ");
for (i = 0; i < 5; i++)
printf ("%d\t", a);

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;
a = 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]

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_algorithm#List_of_sorting_algorithms)

then

http://en.wikipedia.org/wiki/Heapsort

 

[Philip Potter]

Hi all,

Is there a simple algorithm to implement in heapsort???

Heap sort *is* an algorithm. I'm not quite sure what you mean, but I
think you're asking "Is there a simple way to implement the heapsort
algorithm in C?"

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

heapsort (a, 5);

puts ("\n After Sorting:: ");
for (i = 0; i < 5; i++)
printf ("%d\t", a);

puts ("");
return (EXIT_SUCCESS);
}

void
heapsort (int a[5], int size)

The '5' here serves no purpose except to confuse the reader. Leave it
out. In function parameters, an array type really means a pointer type
(in this case, 'int *'). See comp.lang.c FAQ 6.4.

{
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;
a = temp;
siftdown (a, 0, i - 1);
} /*finding the max element & putting in last pos
*/

}

void
siftdown (int a[5], int r, int b)

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

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

It looks fine to me. I do have one question though: why do your function
parameters have such terse names (a,r,b) when your local variables have
much more descriptive (and self-documenting) names (maxchild, temp, done)?

 

[sophia.agnes]

Hi all,

Is there a simple algorithm to implement in heapsort???

Heap sort *is* an algorithm. I'm not quite sure what you mean, but I
think you're asking "Is there a simple way to implement the heapsort
algorithm in C?"

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

heapsort (a, 5);

puts ("\n After Sorting:: ");
for (i = 0; i < 5; i++)
printf ("%d\t", a);

puts ("");
return (EXIT_SUCCESS);
}

void
heapsort (int a[5], int size)

The '5' here serves no purpose except to confuse the reader. Leave it
out. In function parameters, an array type really means a pointer type
(in this case, 'int *'). See comp.lang.c FAQ 6.4.

{
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;
a = temp;
siftdown (a, 0, i - 1);
} /*finding the max element & putting in last pos
*/

}

void
siftdown (int a[5], int r, int b)

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

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

It looks fine to me. I do have one question though: why do your function
parameters have such terse names (a,r,b) when your local variables have
much more descriptive (and self-documenting) names (maxchild, temp, done)?

r is for root really,then for b , i forgot

 

[sophia.agnes]

Hi all,

Is there a simple algorithm to implement in heapsort???

Heap sort *is* an algorithm. I'm not quite sure what you mean, but I
think you're asking "Is there a simple way to implement the heapsort
algorithm in C?"

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

heapsort (a, 5);

puts ("\n After Sorting:: ");
for (i = 0; i < 5; i++)
printf ("%d\t", a);

puts ("");
return (EXIT_SUCCESS);
}

void
heapsort (int a[5], int size)

The '5' here serves no purpose except to confuse the reader. Leave it
out. In function parameters, an array type really means a pointer type
(in this case, 'int *'). See comp.lang.c FAQ 6.4.

{
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;
a = temp;
siftdown (a, 0, i - 1);
} /*finding the max element & putting in last pos
*/

}

void
siftdown (int a[5], int r, int b)

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

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

It looks fine to me. I do have one question though: why do your function
parameters have such terse names (a,r,b) when your local variables have
much more descriptive (and self-documenting) names (maxchild, temp, done)?

BTW r is for root

 

[user923005]

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

heapsort (a, 5);

puts ("\n After Sorting:: ");
for (i = 0; i < 5; i++)
printf ("%d\t", a);

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;
a = 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 -- 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]

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

heapsort (a, 5);

puts ("\n After Sorting:: ");
for (i = 0; i < 5; i++)
printf ("%d\t", a);

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;
a = 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.

 

[Mark Bluemel]

r is for root really

Then why not call it "root"?

,then for b , i forgot

Case proven, mi'lud.

 

[Christopher Benson-Manica]

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

 

[Ben Pfaff]

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.

I like to use [] for a pointer to the first element of an array,
* for a pointer to exactly one element. I find it to be useful
documentation. Except for character strings, where I always
write *, although I didn't realize until just this moment that I
was being inconsistent there.

 

[pete]

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.

I like to use [] for a pointer to the first element of an array,
* for a pointer to exactly one element. I find it to be useful
documentation. Except for character strings, where I always
write *, although I didn't realize until just this moment that I
was being inconsistent there.

I use
int main(int argc, char *argv[]) { /* ... */ }
because I copied it out of the standard;
otherwise, I use pointer notation for parameters.
I prefer pointer notation , instead of array notation,
for parameters, because that shows the parameters
for what they really are: pointers.

I use lower case for the str() and xstr() macros,
because I also copy them out of the standard that way.

 

[Szabolcs Nagy]

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]

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

 

[Christopher Benson-Manica]

I like to use [] for a pointer to the first element of an array,
* for a pointer to exactly one element. I find it to be useful
documentation.

Hm, I suppose that does make sense; perhaps I've merely been corrupted
by a couple of years of Java programming in this respect.

Except for character strings, where I always
write *, although I didn't realize until just this moment that I
was being inconsistent there.

I would think that * would be preferred for character arrays that were
strings, and [] for those that were not.

 

[Charlie Gordon]

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.

 

[Keith Thompson]

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.

 

[Chris Torek]

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