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