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 [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
