By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,760 Members | 1,630 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,760 IT Pros & Developers. It's quick & easy.

Ordered output without "sorting" array

P: n/a
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[i].member > array[last_printer].member && array[i].member <
array[candidate].member

but this quickly got messy so I scrapped it.

Thanks.

--
"Being a social outcast helps you stay | 'f*******@tznvy.pbz'.encode('rot-13')
concentrated on the really important |
things, like thinking and hacking." | [ RENT THIS SPACE ]
- Eric S. Raymond |

Nov 15 '05 #1
Share this Question
Share on Google+
2 Replies


P: n/a
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[i].member > array[last_printer].member && array[i].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[i]] 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.
Nov 15 '05 #2

P: n/a


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[i].member > array[last_printer].member && array[i].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[i] = &array[i];
qsort (pointers, ARRAYSIZE, sizeof pointers[0], compare);
for (i = 0; i < ARRAYSIZE; ++i)
output_a_struct(pointers[i]);

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

--
Er*********@sun.com

Nov 15 '05 #3

This discussion thread is closed

Replies have been disabled for this discussion.