Ordered output without "sorting" array

Discussion in 'C Programming' started by Simon Morgan, Jul 26, 2005.

  1. Simon Morgan

    Simon Morgan Guest

    I hope this isn't OT, I looked for a newsgroup dealing purely with
    algorithms but none were to be found and seeing as I'm trying to implement
    this in C I thought this would be the best place.

    I have an array of structs containing data which I'd like to output
    ordered based on the value of a single member. I was wondering if there is
    a relatively simple way of doing this without actually modifying the
    structure of the array?

    I had a stab at doing this using last_printed and candidate variables
    whereby I'd basically iterate through the array and check that

    array.member > array[last_printer].member && array.member <
    array[candidate].member

    but this quickly got messy so I scrapped it.

    Thanks.

    --
    "Being a social outcast helps you stay | ''.encode('rot-13')
    concentrated on the really important |
    things, like thinking and hacking." | [ RENT THIS SPACE ]
    - Eric S. Raymond |
    Simon Morgan, Jul 26, 2005
    #1
    1. Advertising

  2. Simon Morgan

    Eric Sosman Guest

    Simon Morgan wrote:
    > I hope this isn't OT, I looked for a newsgroup dealing purely with
    > algorithms but none were to be found and seeing as I'm trying to implement
    > this in C I thought this would be the best place.
    >
    > I have an array of structs containing data which I'd like to output
    > ordered based on the value of a single member. I was wondering if there is
    > a relatively simple way of doing this without actually modifying the
    > structure of the array?
    >
    > I had a stab at doing this using last_printed and candidate variables
    > whereby I'd basically iterate through the array and check that
    >
    > array.member > array[last_printer].member && array.member <
    > array[candidate].member


    One way would be to set up a parallel array containing
    pointers to the structs in the inviolable array, use qsort()
    to sort the array of pointers, and then traverse them:

    struct thing {
    int member;
    float check;
    double trouble;
    } array[] = {
    { 42, 1.0, 3.1 },
    { -6, 0.9, 2.7 },
    ...
    };
    #define ARRAYSIZE (sizeof array / sizeof array[0])
    struct thing *pointers[ARRAYSIZE];

    ...

    int compare(const void *p, const void *q) {
    /* pointers to the elements of pointers[] */
    const struct thing **r = p, **s = q;
    /* pointers to the elements of array[] */
    const struct thing *x = *r, *y = *s;
    /* compare the array[] elements */
    return (x->member > y->member) - (x->member < y->member);
    }

    ...


    for (i = 0; i < ARRAYSIZE; ++i)
    pointers = &array;
    qsort (pointers, ARRAYSIZE, sizeof pointers[0], compare);
    for (i = 0; i < ARRAYSIZE; ++i)
    output_a_struct(pointers);

    (This could be written more concisely; I've presented it
    in verbose form for clarity's sake.) What you're doing
    here is akin to alphabetizing a library's card catalog
    without rearranging the books on its shelves.

    --
    Eric Sosman, Jul 26, 2005
    #2
    1. Advertising

  3. Simon Morgan

    Michael Mair Guest

    Simon Morgan wrote:
    > I hope this isn't OT, I looked for a newsgroup dealing purely with
    > algorithms but none were to be found and seeing as I'm trying to implement
    > this in C I thought this would be the best place.
    >
    > I have an array of structs containing data which I'd like to output
    > ordered based on the value of a single member. I was wondering if there is
    > a relatively simple way of doing this without actually modifying the
    > structure of the array?
    >
    > I had a stab at doing this using last_printed and candidate variables
    > whereby I'd basically iterate through the array and check that
    >
    > array.member > array[last_printer].member && array.member <
    > array[candidate].member
    >
    > but this quickly got messy so I scrapped it.


    comp.programming is a good address for algorithmic questions.

    <OT>Your approach typically has quadratic complexity.
    If you do not want to order the array itself, consider having an
    index array ind which contains the numbers from 0 through
    (sizeof array/sizeof array[0] - 1) which are sorted in a way that
    array[ind] is output ordered for i=0,1,...
    You can sort this array easily with an algorithm with better time
    complexity without losing the original order.
    </OT>

    As we are in comp.lang.c, I just can warn you that if member is a
    floating point number, the usual caveats (see comp.lang.c FAQ:
    Equality is not "sharp" in this case as you usually cannot even add
    ten times 0.1 and arrive at 1.0) apply.


    Cheers
    Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
    Michael Mair, Jul 26, 2005
    #3
    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. Newbie
    Replies:
    1
    Views:
    521
    Andrew Thompson
    Apr 7, 2004
  2. Arvind Ganesan

    ordered list (OL) tag with tables

    Arvind Ganesan, Sep 6, 2003, in forum: HTML
    Replies:
    10
    Views:
    10,503
    Nico Schuyt
    Sep 6, 2003
  3. Trans
    Replies:
    11
    Views:
    237
    Rick DeNatale
    Sep 5, 2006
  4. Scott Bass
    Replies:
    4
    Views:
    155
    Big and Blue
    Mar 21, 2005
  5. DL

    Ordered list inside ordered list

    DL, Nov 9, 2009, in forum: Javascript
    Replies:
    6
    Views:
    324
    Dr J R Stockton
    Nov 21, 2009
Loading...

Share This Page