How can I make this code less ugly?

[gw7rib]

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 cross-posting 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 = (n-1)/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=(y-1)/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.

 

[Noah Roberts]

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.

 

[Tak-Shing Chan]

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

Tak-Shing

 

[Simon Biber]

Nope, the code is C.

The code you quoted is valid in both C and C++.

The code you snipped is not C:

The initialiser for h is not a constant expression in C.

 

[Dietmar Schindler]

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;

 

[gw7rib]

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.

 

[red floyd]

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

 

[Noah Roberts]

The code you quoted is valid in both C and C++.

Those headers don't exist in C++.

 

[Alf P. Steinbach]

* Noah Roberts:

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

Cross-posting to clc and clc++ is evil.

 

[Simon Biber]

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
<cstdio> style header names.

 

[Default User]

Those headers don't exist in C++.

OT, but yes they do. They are deprecated, but perfectly standard. The
headers <cstdio>, <cstdlib>, and <climits> are prefered.



Brian