Ordered output without "sorting" array

S

Simon Morgan

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

Eric Sosman

Simon said:
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.
 
M

Michael Mair

Simon said:
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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,733
Messages
2,569,440
Members
44,830
Latest member
ZADIva7383

Latest Threads

Top