Velocity Reviews > C++ > How can I make this code less ugly?

# How can I make this code less ugly?

gw7rib@aol.com
Guest
Posts: n/a

 07-10-2006
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

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?

Paul.

Noah Roberts
Guest
Posts: n/a

 07-10-2006

http://www.velocityreviews.com/forums/(E-Mail Removed) 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.

Tak-Shing Chan
Guest
Posts: n/a

 07-10-2006
On Mon, 10 Jul 2006 (E-Mail Removed) 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)) {

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
Guest
Posts: n/a

 07-11-2006
Noah Roberts wrote:
> (E-Mail Removed) 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 = (n-1)/2;

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

--
Simon.

Dietmar Schindler
Guest
Posts: n/a

 07-13-2006
(E-Mail Removed) 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

gw7rib@aol.com
Guest
Posts: n/a

 07-13-2006

Dietmar Schindler wrote:
> (E-Mail Removed) 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.

red floyd
Guest
Posts: n/a

 07-13-2006
(E-Mail Removed) wrote:
> Dietmar Schindler wrote:
>> (E-Mail Removed) 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.
}

Noah Roberts
Guest
Posts: n/a

 07-14-2006

Simon Biber wrote:
> Noah Roberts wrote:
> > (E-Mail Removed) 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++.

Alf P. Steinbach
Guest
Posts: n/a

 07-14-2006
* Noah Roberts:
> Simon Biber wrote:
>> Noah Roberts wrote:
>>> (E-Mail Removed) 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++.

Cross-posting 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: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

Simon Biber
Guest
Posts: n/a

 07-14-2006
Noah Roberts wrote:
> Simon Biber wrote:
>> Noah Roberts wrote:
>>> (E-Mail Removed) 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

--
Simon.