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/ --