Re: Sorting data points
If I think about it, this definitely isn't the quicksort. However, it
may be that it is mathematically equivalent to the heapsort. In fact,
it may be an easy implementation of the heap sort.
Anyhow, when I was looking back at the data, the same Nlog2N factor came
out, and www.nr.com at least claims that they actually get that in their
worst case. In which case, they may be mathematically equivalent.
The two methods are, at least, conceptually equivalent in terms of the
general method.
So if you wanted to use a standard algorithm, I guess I'd advocate the
heapsort.
But it's not quite the same as the one I described.
- Michael
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
--
To UNSUBSCRIBE, email to debian-user-request@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org
Reply to: