Re: Sorting data points
Tinus Kotze wrote:
>
> On Sun 05 May 02 16:03, DSC Siltec wrote:
> > Deosaran Bisnath wrote:
> > > I am new to linux g++ & am not sure how to do this. Your help is
> > > most welcome
> > >
> > > there are about 50 data points like this, x and y
> > >
> > > x y
> > > 2.4 1
> > > 67.21 2
> > > 1.9 3
> > > 211.45 4
> > >
> > > I want to sort x in ascending or descending order so the above are
> > > arranged like this:
> > >
> > > x y
> > > 211.45 4
> > > 67.21 2
> > > 2.4 1
> > > 1.9 3
> > >
> > > what is the fastest way to do this? thanks
> >
> > The fastest way probably isn't well published.
> > First of all, to increase speed, use indexes. That is, you don't
> > change the
> > order of the list items -- rather, each list has not only an X entry
> > and a Y entry, but also 4 other entries "Previous item on X list",
> > "Next item on X list", "Previous item on Y list", "Next item on Y
> > list". Then you have 4 other indexes: "First item on X list", "Last
> > item on X list"... and so on.
> >
> > Aside from that, if you are going to be deleting items, you should
> > also keep a trash list as well.
> >
> > This all prevents you from having to move whole lists of data.
> > Rather, you just change the pointers and go on.
> >
> > ---- Now ---- here's the algorithm for the *FASTEST* sort of a
> > general nature.
> >
> > What do I mean by fastest? The number of compares approaches the
> > magical
> > number of data reduction, Log-2-N. Let's see.
> >
> > (1) Go through the items in pairs. Compare the first item with the
> > second item in each pair. If the first item comes before the second
> > item, then leave it alone. If the first item comes after the second
> > item, then swap them.
> >
> > (2) Now go through the list in pairs of pairs. Compare the top two
> > items from the list, and make the first item first. Now compare the
> > "loser" with the next item in the previous winner's list. Make the
> > next item second. Now -- if both winners came from the same list,
> > then you're done with that "pair of pairs". If both winners came
> > from a different list, then you need one more compare.
> >
> > So now you should have groups of 4 that are each ordered.
> >
> > (3) Now go through the list in pairs of "4s". Take two groups of
> > four, and compare the top items. Keep the winner, and compare the
> > loser to the item below the winner. Keep that winner, and advance
> > through both "stacks" of numbers until one stack is exhausted. Then
> > stack the remainder on the bottom.
> >
> > (4) Subsequently go through the list in pairs of 8s, 16s, etc... If
> > at the end of the list you don't have a power of 2, it doesn't
> > matter. Just do your compares until one stack runs out, and stack the
> > rest on the bottom of that resultant stack. Eventually, you will
> > have a single stack, all sorted.
> >
> > You will best be able to understand this method by trying it with a
> > deck of cards. First do it with 16 cards (A-2-3-... 10,J,Q,13 of
> > hearts, and 2-3-4 of spades). Then try it with the full deck. Then
> > go program it.
> >
> >
> > - Michael
>
> Just for interest sake, are you refering to the quicksort algoritm, or
> another.
>
> Tinus
I don't think that this is at all like the quicksort method.
The quicksort method averages very well -- but can take up to N-squared
comparisons. So I think that the routine I named is actually better.
- Michael
--
To UNSUBSCRIBE, email to debian-user-request@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org
Reply to: