Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Ordered output without "sorting" array

Reply
Thread Tools

Ordered output without "sorting" array

 
 
Simon Morgan
Guest
Posts: n/a
 
      07-26-2005
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 | '(E-Mail Removed)'.encode('rot-13')
concentrated on the really important |
things, like thinking and hacking." | [ RENT THIS SPACE ]
- Eric S. Raymond |

 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      07-26-2005


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.

--
http://www.velocityreviews.com/forums/(E-Mail Removed)

 
Reply With Quote
 
 
 
 
Michael Mair
Guest
Posts: n/a
 
      07-26-2005
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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Ordered list inside ordered list DL Javascript 6 11-21-2009 11:43 PM
Ordered contrast for String or Array Trans Ruby 11 09-05-2006 01:18 AM
Read string from multiple files, output ordered by a 2nd file Scott Bass Perl Misc 4 03-21-2005 05:59 PM
Help Please : - Retrieve object key held in an ordered linked list node Newbie Java 1 04-06-2004 11:12 PM
ordered list (OL) tag with tables Arvind Ganesan HTML 10 09-06-2003 09:47 PM



Advertisments