What is the cost for a swap vs copying to and from another location? On Fri, Apr 20, 2018 at 2:45 PM Marc LeBrun <mlb@well.com> wrote:
If preprocessing is truly free, then at worst you need only simulate each of the N different scenarios without actually moving the associated data and see which one would be cheapest. (ie run through the cases, for k=0..N-1, simulating sorting the permutation using the predicates Pk := i < j just when (i-k)\N < (j-k)\N)
Perhaps for a specific sorting algorithm you can compute the merit for each Pk more directly, without actually undertaking the simulation, thus being cheaper than free.
On Apr 20, 2018, at 11:14 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Yes, a radix-style sort will work; I had forgotten about that.
I'm working on a model where every access is expensive, and RAM access is not even remotely constant time.
In this particular problem, I can *preprocess for free* to determine the complete permutation, but then I have to pay full retail price for actually applying this permutation to rearrange the data records.
I was hoping to minimize rearrangements in the cases where the data was already "almost sorted".
I was thinking along the lines of Quicksort, which is pretty good when the data is already almost sorted.
At 10:05 AM 4/20/2018, Tomas Rokicki wrote:
A linear walk can notice and preserve the cyclic walk else abort. For what disorder distribution do you want to do better?
If you have such a field as you describe radix sort is linear time, as discussed in TAOCP.
On Fri, Apr 20, 2018 at 12:56 PM Henry Baker <hbaker1@pipeline.com> wrote:
Suppose you have N records in which one of the fields is a number 0..(N-1), and there is exactly one record for each number 0..(N-1).
It is trivial to sort such a set using traditional Knuth-TAOCP algorithms.
However, if I don't care that the first record is labelled "0", but only care that the final ordering preserves the *cyclic* ordering of the group, can I do any better?
Obviously, I can't do a lot better, since cyclicly rotating the ordering costs O(N), while sorting costs O(NlogN), but is there a clever way to sort w/o putting "0" at the front and "(N-1)" at the end? In particular, is there a way to sort that automatically notices when the records are already in cyclic order, and doesn't bother making any further changes. -- http://cube20.org/ -- http://golly.sf.net/ --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --