Re: Sorting data points
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
--
To UNSUBSCRIBE, email to debian-user-request@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org
Reply to: