I have written a sorting program, to try to understand how heapsort
works. Unfortunately, considering it's supposed to help my
understanding, one line of it has got very ugly and so I was wondering
if anyone had any advice on how to make it clearer.
The code is C++, but I am rashly crossposting to comp.lang.c as the
part I am having difficulty with is the same as C and I thought the
peoplr there might also be able to help. You can make it a proper C
program by replacing the definition of n with a #define. I'm aware that
the sort is not actually a heapsort, but I think I know where I'm going
there. I also appreciate that it is only a "toy" program at present and
if I was going to put it to proper use I would be better with a
function pointer for the comparison.
So here is the code:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h// for INT_MAX
const int n = 11;
const int h = (n1)/2;
typedef int VAL;
const VAL EMPTY = INT_MAX;
/* Special casing would be necessary if n was even. Code also assumes
EMPTY is bigger than real values. */
int main(void) {
int x, y, z, z1, z2;
VAL a[n], b[n], c[n], t;
for (x=0; x < n; x++)
a[x] = rand() % 1000;
printf("Unsorted:");
for (x=0; x < n; x++)
printf(" %d", a[x]);
printf("\n\n");
/* Put values into b, in such a way that b[x] is always less than or
equal to both b[2x+1] and b[2x+2] (where x < h). This can be done
in O(n log n) and could if necessary be done in place in a. */
for (x = 0; x < n; x++) {
t = a[x];
y = x;
while (y 0 && t < b[z=(y1)/2]) {
b[y] = b[z];
y = z; }
b[y] = t; }
/* Now pull them out again */
for (x = 0; x < n; x++) {
c[x] = b[0];
y = 0;
while (y < h && (b[z2=2*y+2,z1=2*y+1] < EMPTY  b[z2] < EMPTY)) {
if(b[z1] <= b[z2]) { b[y] = b[z1]; y = z1; }
else { b[y] = b[z2]; y = z2; } }
b[y] = EMPTY; }
printf("Sorted:");
for (x=0; x < n; x++)
printf(" %d", c[x]);
printf("\n\n");
return 0;
}
The snag is with the while statement which sets up the values of z1 and
z2. My first attempt at the program had:
while (y < h && (b[z1=2*y+1] < EMPTY  b[z2=2*y+2] < EMPTY)) {
which is still somewhat messy, but this had the disadvantage of not
working (the program ran forever). The snag with that version is that,
if b[z1] is not empty, the value of z2 does not get set. Hence I have
changed it to the abomination above.
Can anyone advise how to make it clearer?
Thanks for your help.
Paul. 10 1446 gw****@aol.com wrote:
The code is C++
So here is the code:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h// for INT_MAX
Nope, the code is C.
On Mon, 10 Jul 2006 gw****@aol.com wrote:
I have written a sorting program, to try to understand how heapsort
works. Unfortunately, considering it's supposed to help my
understanding, one line of it has got very ugly and so I was wondering
if anyone had any advice on how to make it clearer.
[snip]
y = 0;
while (y < h && (b[z2=2*y+2,z1=2*y+1] < EMPTY  b[z2] < EMPTY)) {
How about this:
for (y = 0, z1 = 1, z2 = 2;
y < h && (b[z1] < EMPTY  b[z2] < EMPTY);
z1 = 2 * y + 1, z2 = 2 * y + 2) {
TakShing
Noah Roberts wrote:
gw****@aol.com wrote:
>The code is C++
>So here is the code:
#include <stdio.h> #include <stdlib.h> #include <limits.h// for INT_MAX
Nope, the code is C.
The code you quoted is valid in both C and C++.
The code you snipped is not C:
>const int n = 11; const int h = (n1)/2;
The initialiser for h is not a constant expression in C.

Simon. gw****@aol.com wrote:
while (y < h && (b[z2=2*y+2,z1=2*y+1] < EMPTY  b[z2] < EMPTY)) {
if(b[z1] <= b[z2]) { b[y] = b[z1]; y = z1; }
else { b[y] = b[z2]; y = z2; } }
while (y < h && (z1=2*y+1, z2=2*y+2, b[z1] < EMPTY  b[z2] < EMPTY))
if (b[z1] <= b[z2]) b[y] = b[z1], y = z1;
else b[y] = b[z2], y = z2;
or
while (y < h && (z = 2*y, b[z+1] < EMPTY  b[z+2] < EMPTY))
if (b[z+1] <= b[z+2]) b[y] = b[z+1], y = z+1;
else b[y] = b[z+2], y = z+2;
or
while (y < h && (b[2*y+1] < EMPTY  b[2*y+2] < EMPTY))
z = 2*y + (b[2*y+1] <= b[2*y+2] ? 1 : 2), b[y] = b[z], y = z;
or
while (y < h && (z = 2*y, b[z+1] < EMPTY  b[z+2] < EMPTY))
z += b[z+1] <= b[z+2] ? 1 : 2, b[y] = b[z], y = z;

Dietmar
Dietmar Schindler wrote:
gw****@aol.com wrote:
while (y < h && (b[z2=2*y+2,z1=2*y+1] < EMPTY  b[z2] < EMPTY)) {
if(b[z1] <= b[z2]) { b[y] = b[z1]; y = z1; }
else { b[y] = b[z2]; y = z2; } }
while (y < h && (z1=2*y+1, z2=2*y+2, b[z1] < EMPTY  b[z2] < EMPTY))
if (b[z1] <= b[z2]) b[y] = b[z1], y = z1;
else b[y] = b[z2], y = z2;
or
while (y < h && (z = 2*y, b[z+1] < EMPTY  b[z+2] < EMPTY))
if (b[z+1] <= b[z+2]) b[y] = b[z+1], y = z+1;
else b[y] = b[z+2], y = z+2;
or
while (y < h && (b[2*y+1] < EMPTY  b[2*y+2] < EMPTY))
z = 2*y + (b[2*y+1] <= b[2*y+2] ? 1 : 2), b[y] = b[z], y = z;
or
while (y < h && (z = 2*y, b[z+1] < EMPTY  b[z+2] < EMPTY))
z += b[z+1] <= b[z+2] ? 1 : 2, b[y] = b[z], y = z;
Thanks for your suggestions. I think the first option may be the one to
go for  setting both the values of z1 and z2 before mentioning b.
Either that, or miss out the z's completely  more like your second
option. gw****@aol.com wrote:
Dietmar Schindler wrote:
>gw****@aol.com wrote:
>> while (y < h && (b[z2=2*y+2,z1=2*y+1] < EMPTY  b[z2] < EMPTY)) { if(b[z1] <= b[z2]) { b[y] = b[z1]; y = z1; } else { b[y] = b[z2]; y = z2; } }
while (y < h && (z1=2*y+1, z2=2*y+2, b[z1] < EMPTY  b[z2] < EMPTY)) if (b[z1] <= b[z2]) b[y] = b[z1], y = z1; else b[y] = b[z2], y = z2;
or
while (y < h && (z = 2*y, b[z+1] < EMPTY  b[z+2] < EMPTY)) if (b[z+1] <= b[z+2]) b[y] = b[z+1], y = z+1; else b[y] = b[z+2], y = z+2;
or
while (y < h && (b[2*y+1] < EMPTY  b[2*y+2] < EMPTY)) z = 2*y + (b[2*y+1] <= b[2*y+2] ? 1 : 2), b[y] = b[z], y = z;
or
while (y < h && (z = 2*y, b[z+1] < EMPTY  b[z+2] < EMPTY)) z += b[z+1] <= b[z+2] ? 1 : 2, b[y] = b[z], y = z;
Thanks for your suggestions. I think the first option may be the one to
go for  setting both the values of z1 and z2 before mentioning b.
Either that, or miss out the z's completely  more like your second
option.
How about moving the test into a separate function as well
while (myCondition())
{
// option 1 code.
}
Simon Biber wrote:
Noah Roberts wrote:
gw****@aol.com wrote:
The code is C++
So here is the code:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h// for INT_MAX
Nope, the code is C.
The code you quoted is valid in both C and C++.
Those headers don't exist in C++.
* Noah Roberts:
Simon Biber wrote:
>Noah Roberts wrote:
>>gw****@aol.com wrote: The code is C++ So here is the code:
#include <stdio.h> #include <stdlib.h> #include <limits.h// for INT_MAX Nope, the code is C.
The code you quoted is valid in both C and C++.
Those headers don't exist in C++.
They do exist in C++.
The code is pure C, specifically C99, with no trace of C++; it does
contain an error (the const initializer mentioned elsethread), but that
does not make it C++.
Crossposting to clc and clc++ is evil.

A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Topposting.
Q: What is the most annoying thing on usenet and in email?
Noah Roberts wrote:
Simon Biber wrote:
>Noah Roberts wrote:
>>gw****@aol.com wrote: The code is C++ So here is the code:
#include <stdio.h> #include <stdlib.h> #include <limits.h// for INT_MAX Nope, the code is C.
The code you quoted is valid in both C and C++.
Those headers don't exist in C++.
Yes they do. They are still valid in C++.
C++ doesn't force existing code to change to the new and preferred
<cstdiostyle header names.

Simon.
Noah Roberts wrote:
>
Simon Biber wrote:
Noah Roberts wrote:
gw****@aol.com wrote:
>The code is C++
>
>So here is the code:
>#include <stdio.h>
>#include <stdlib.h>
>#include <limits.h// for INT_MAX
>
Nope, the code is C.
The code you quoted is valid in both C and C++.
Those headers don't exist in C++.
OT, but yes they do. They are deprecated, but perfectly standard. The
headers <cstdio>, <cstdlib>, and <climitsare prefered.
Brian This discussion thread is closed Replies have been disabled for this discussion. Similar topics
9 posts
views
Thread by Pedro Graca 
last post: by

25 posts
views
Thread by Johan Bergman 
last post: by

7 posts
views
Thread by Skybuck Flying 
last post: by

26 posts
views
Thread by William L. Bahn 
last post: by

14 posts
views
Thread by Steven D'Aprano 
last post: by

60 posts
views
Thread by Dave 
last post: by

9 posts
views
Thread by Joel Hedlund 
last post: by

10 posts
views
Thread by gw7rib 
last post: by

18 posts
views
Thread by lovecreatesbea... 
last post: by

52 posts
views
Thread by Paul McGuire 
last post: by
          