If you know that each record contains a unique label from 0 to N-1, you can sort in linear time and linear space without relaxing the sort requirement to allow cyclic permutations; just look at each element and put it where it goes. No algorithm that looks at all the data can be appreciably faster than this. Andy On Fri, Apr 20, 2018 at 12:52 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.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com