| Author |
Message |
|
Matt Silberstei
#1 / 25
|
 Slightly OT: sorting This is not actually a C question, but I have a sorting problem
and figured that C programmers would be able to help.
I have about 500 CDs. They are currently essentially randomized.*
I would like to alphabetize them. What is the best method to use?
TIA.
--
Matt Silberstein
Observation favors the stable, the persistent
|
| Thu, 17 Feb 2005 11:55:54 GMT |
|
 |
|
Ben Pfaf
#2 / 25
|
Slightly OT: sorting Quote:
> I have about 500 CDs. They are currently essentially randomized.*
> I would like to alphabetize them. What is the best method to use?
Use a hybrid postal/insertion sort. In the first pass,
distribute into 26 piles[1] based on the first letter in the sort
key. In the second pass, sort each pile with insertion sort.
Finally, stack the piles.
Followups set.
[1] Or more or fewer depending on the language of the key.
|
| Thu, 17 Feb 2005 12:01:04 GMT |
|
|
|
R124c4
#3 / 25
|
Slightly OT: sorting Quote: Matt Silberstein writes: >This is not actually a C question, but I have a sorting problem >and figured that C programmers would be able to help. >I have about 500 CDs. They are currently essentially randomized.*
>I would like to alphabetize them. What is the best method to use?
comes with all valid C compilers. But that assumes the data is already in or
should be put in a data base of some kind. There may already be some kind of
mini data base program that came with your computer. It might provide some
provisions for sorting.
|
| Thu, 17 Feb 2005 19:07:49 GMT |
|
|
|
David Rubi
#4 / 25
|
Slightly OT: sorting Quote:
> I have about 500 CDs. They are currently essentially randomized.*
> I would like to alphabetize them. What is the best method to use?
Ask your friends for help. Make a party out of it.
david
--
If 91 were prime, it would be a counterexample to your conjecture.
-- Bruce Wheeler
|
| Sun, 20 Feb 2005 00:23:56 GMT |
|
|
|
Matt Silberste
#5 / 25
|
Slightly OT: sorting Quote:
> This is not actually a C question, but I have a sorting problem > and figured that C programmers would be able to help. > I have about 500 CDs. They are currently essentially randomized.*
> I would like to alphabetize them. What is the best method to use?
> TIA.
Thank you. That is what I figured, but wanted to make sure. I will
probably combine U-Z, but otherwise that makes sense. Given the small
amout of cache (my failing memory) and expensive moves (failing
joints) this sounds like the best way.
|
| Sun, 20 Feb 2005 01:30:15 GMT |
|
|
|
Matt Silberste
#6 / 25
|
Slightly OT: sorting Quote:
> Matt Silberstein writes: > >This is not actually a C question, but I have a sorting problem
> >and figured that C programmers would be able to help.
> >I have about 500 CDs. They are currently essentially randomized.*
> >I would like to alphabetize them. What is the best method to use?
> A C programmer would instinctively think of the qsort() sorting routine that
> comes with all valid C compilers. But that assumes the data is already in or
> should be put in a data base of some kind. There may already be some kind of
> mini data base program that came with your computer. It might provide some
> provisions for sorting.
Sorry I was not clear. It would be easy if I had the info in a DB,
computer time is free. I did not want to bother to do that, so I
actually needed an efficient sort method.
Thanks though.
|
| Sun, 20 Feb 2005 01:31:13 GMT |
|
|
|
Dik T. Winte
#7 / 25
|
Slightly OT: sorting
> > >I have about 500 CDs. They are currently essentially randomized.*
> > >I would like to alphabetize them. What is the best method to use?
...
> Sorry I was not clear. It would be easy if I had the info in a DB,
> computer time is free. I did not want to bother to do that, so I
> actually needed an efficient sort method.
Pick up a CD. Go along the remainder of the CD's, if you find one
that should be earlier in your alphabetical list, exchange them.
Continue until you have gone through all your CD's. Set the CD
thus found apart in a new row. Do the same with the second CD.
Continue until you are done.
An alternative way. Put your CD's in a row. Go through the adjacent
pairs of CD's in the row. If the order is wrong exchange them.
Continue to the end. Restart the process for a next scan. When
during a scan you find there is no need to exchange, you are done.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
|
| Sun, 20 Feb 2005 08:45:01 GMT |
|
|
|
Eric G. Mille
#8 / 25
|
Slightly OT: sorting
Quote:
> > > >I have about 500 CDs. They are currently essentially randomized.* > > > >I would like to alphabetize them. What is the best method to use? > ... > > Sorry I was not clear. It would be easy if I had the info in a DB, > > computer time is free. I did not want to bother to do that, so I > > actually needed an efficient sort method. > Pick up a CD. Go along the remainder of the CD's, if you find one
> that should be earlier in your alphabetical list, exchange them.
> Continue until you have gone through all your CD's. Set the CD
> thus found apart in a new row. Do the same with the second CD.
> Continue until you are done.
> An alternative way. Put your CD's in a row. Go through the adjacent
> pairs of CD's in the row. If the order is wrong exchange them.
> Continue to the end. Restart the process for a next scan. When
> during a scan you find there is no need to exchange, you are done.
Jeez! 500 items? Even the slowest sort methods would probably be
fast enough and the standard qsort() usually does quite well.
$ ls *.iso > sorted.file
|
| Sun, 20 Feb 2005 12:36:45 GMT |
|
|
|
those who know me have no need of my nam
#9 / 25
|
Slightly OT: sorting [fu-t set]
in comp.lang.c i read:
Quote:
>> > > >I have about 500 CDs. They are currently essentially randomized.*
>> > > >I would like to alphabetize them. What is the best method to use?
>$ ls *.iso > sorted.file
provided that your shell sorts as you would desire.
--
bringing you boring signatures for 17 years
|
| Sun, 20 Feb 2005 15:49:31 GMT |
|
|
|
Bruce
#10 / 25
|
Slightly OT: sorting
Quote:
> > > >I have about 500 CDs. They are currently essentially randomized.* > > > >I would like to alphabetize them. What is the best method to use? > ... > > Sorry I was not clear. It would be easy if I had the info in a DB, > > computer time is free. I did not want to bother to do that, so I > > actually needed an efficient sort method. > Pick up a CD. Go along the remainder of the CD's, if you find one
> that should be earlier in your alphabetical list, exchange them.
> Continue until you have gone through all your CD's. Set the CD
> thus found apart in a new row. Do the same with the second CD.
> Continue until you are done.
> An alternative way. Put your CD's in a row. Go through the adjacent
> pairs of CD's in the row. If the order is wrong exchange them.
> Continue to the end. Restart the process for a next scan. When
> during a scan you find there is no need to exchange, you are done.
LOL. How about this: pick up the first CD, and put it in a new row. Pick up
the second, and put it in the new row, on the left or right of the first as
determined by your order. Pick up the third, and put *it* in the correct
place among the first two. Continue until all the CDs are in the new row.
I've actually done manual insertion sorts, e.g. moving books from boxes to
shelves.
Now how could he effectively stack his CDs in a binary tree, without using
adhesives?
|
| Sun, 20 Feb 2005 23:01:07 GMT |
|
|
|
Richard Heathfiel
#11 / 25
|
Slightly OT: sorting
<snip>
Quote: > Now how could he effectively stack his CDs in a binary tree, without using
> adhesives?
Grab a CD from somewhere behind you.
Find two people who are standing closer to Ben Pfaff than you are (let's
call them Lefty and Righty), and tell them to read this article.
Keep grabbing CDs from behind you (until you run out, obviously); for
each CD, simply compare it to the one in your hands. If it's the same,
put it in your pocket. Otherwise, if it's lexographically earlier than
yours, hand it to Lefty; otherwise, hand it to Righty.
--
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
|
| Mon, 21 Feb 2005 01:14:25 GMT |
|
|
|
Dann Corbi
#12 / 25
|
Slightly OT: sorting
Quote:
> <snip>
> > Now how could he effectively stack his CDs in a binary tree, without
using
> > adhesives?
> Grab a CD from somewhere behind you.
> Find two people who are standing closer to Ben Pfaff than you are (let's
> call them Lefty and Righty), and tell them to read this article.
> Keep grabbing CDs from behind you (until you run out, obviously); for
> each CD, simply compare it to the one in your hands. If it's the same,
> put it in your pocket. Otherwise, if it's lexographically earlier than
> yours, hand it to Lefty; otherwise, hand it to Righty.
That's a B+ tree, unless you have clones of Lefty and Righty.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. FAQ: ftp://cap.connx.com/pub/Chess%20Analysis%20Project%20FAQ.htm
|
| Mon, 21 Feb 2005 02:50:56 GMT |
|
|
|
Richard Heathfiel
#13 / 25
|
Slightly OT: sorting Quote:
> > <snip>
> > > Now how could he effectively stack his CDs in a binary tree, without
> using
> > > adhesives?
> > Grab a CD from somewhere behind you.
> > Find two people who are standing closer to Ben Pfaff than you are (let's
> > call them Lefty and Righty), and tell them to read this article.
> > Keep grabbing CDs from behind you (until you run out, obviously); for
> > each CD, simply compare it to the one in your hands. If it's the same,
> > put it in your pocket. Otherwise, if it's lexographically earlier than
> > yours, hand it to Lefty; otherwise, hand it to Righty.
> That's a B+ tree, unless you have clones of Lefty and Righty.
Ah, I think you missed the bit where Lefty and Righty were asked to read
the article. :-) It's each person's responsibility to find the next
couple of people standing nearer Ben than they are.
There is a bug in the algorithm, though, which is that Ben himself would
not be able to use it effectively (unless he can work out a way to clone
*himself*, of course!).
--
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
|
| Mon, 21 Feb 2005 04:13:43 GMT |
|
|
|
Damond Lee Walk
#14 / 25
|
Slightly OT: sorting
: I have about 500 CDs. They are currently essentially randomized.*
: I would like to alphabetize them. What is the best method to use?
I favor the "do your own homework" method. Doesn't always work fast but if you work *real* hard it will work itself
out in the end.
If the data is really randomized then just look at the qsort() function.
D.
|
| Mon, 21 Feb 2005 08:47:43 GMT |
|
|
|
Kevin Goodsel
#15 / 25
|
Slightly OT: sorting
Quote:
>: I have about 500 CDs. They are currently essentially randomized.*
>: I would like to alphabetize them. What is the best method to use?
>I favor the "do your own homework" method. Doesn't always work fast but if you work *real* hard it will work itself
>out in the end.
>If the data is really randomized then just look at the qsort() function.
>D.
I'm having a hard time figuring out how to write a comparison function
for qsort to compare two of my CDs. Also, how can I pass the array of
CDs to qsort?
-Kevin
|
| Mon, 21 Feb 2005 10:17:38 GMT |
|
| |
