How can I make this code less ugly?

Discussion in 'C++' started by gw7rib@aol.com, Jul 10, 2006.

  1. Guest

    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.
    , Jul 10, 2006
    #1
    1. Advertising

  2. Noah Roberts Guest

    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.
    Noah Roberts, Jul 10, 2006
    #2
    1. Advertising

  3. On Mon, 10 Jul 2006 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) {

    Tak-Shing
    Tak-Shing Chan, Jul 10, 2006
    #3
  4. Simon Biber Guest

    Noah Roberts wrote:
    > 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.
    Simon Biber, Jul 11, 2006
    #4
  5. 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, Jul 13, 2006
    #5
  6. Guest

    Dietmar Schindler wrote:
    > 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.
    , Jul 13, 2006
    #6
  7. red floyd Guest

    wrote:
    > Dietmar Schindler wrote:
    >> 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.
    }
    red floyd, Jul 14, 2006
    #7
  8. Noah Roberts Guest

    Simon Biber wrote:
    > Noah Roberts wrote:
    > > 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, Jul 14, 2006
    #8
  9. * Noah Roberts:
    > Simon Biber wrote:
    >> Noah Roberts wrote:
    >>> 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?
    Alf P. Steinbach, Jul 14, 2006
    #9
  10. Simon Biber Guest

    Noah Roberts wrote:
    > Simon Biber wrote:
    >> Noah Roberts wrote:
    >>> 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
    <cstdio> style header names.

    --
    Simon.
    Simon Biber, Jul 14, 2006
    #10
  11. Default User Guest

    Noah Roberts wrote:

    >
    > Simon Biber wrote:
    > > Noah Roberts wrote:
    > > > 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 <climits> are prefered.



    Brian
    Default User, Jul 14, 2006
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    10
    Views:
    467
    Default User
    Jul 14, 2006
  2. jiajia wu
    Replies:
    0
    Views:
    344
    jiajia wu
    Oct 1, 2009
  3. 6668
    Replies:
    0
    Views:
    140
  4. lllll
    Replies:
    0
    Views:
    120
    lllll
    Jun 8, 2009
  5. PerlFAQ Server
    Replies:
    0
    Views:
    99
    PerlFAQ Server
    Feb 4, 2011
Loading...

Share This Page