On 14Dec2008 01:42, Marko Vojinovic <vvmarko@xxxxxxxxxxx> wrote: | On Sunday 14 December 2008 00:17, Cameron Simpson wrote: | > On 13Dec2008 19:22, David Hl??ik <david@xxxxxxxxx> wrote: | > | i am really sorry for making offtopic, hope you will not kill me, but | > | this is for me life important problem which needs to be solved within | > | next 12 hours.. | > | I have to create stable algorithm for sorting n numbers from interval | > | [1,n^2] with time complexity O(n) . | > | > Since sorting in general is O(n log n), I don't see how you're going to | > do in in O(n) unless there's something special about your number range | > you've not told us about. A stable sort limits your choices somewhat | > more, but not a lot - it usually just imposes a little more care on the | > comparison stage for most algorithms. | > | > I think you need to define the problem in more detail. | | There is the generation counter algorithm. It is O(n), and relies on the fact | that one knows the boundaries of the possible elements of the dataset (and | it's domain). Basically, you simply count the number of appearances of every | element in your set. It's just a single for-loop. Hmm. Cute. But what about to insertion cost of updating the counters? That's where this kind of thing tends to come back on you. | Of course, if you don't know this additional data, the general sort is | O(n ln n) at best. However, the OP did state that he needs to sort integers | from the interval [1,n^2] which is enough for generation counter. | | The OP also posted this to the CentOS list as well, and I gave him a more | thorough explanation there. You might want to take a look. ;-) I'm not on that list (and am having trouble finding out how to join). Can you send me a copy or point me to an archive URL? Cheers, -- Cameron Simpson <cs@xxxxxxxxxx> DoD#743 http://www.cskk.ezoshosting.com/cs/ -- fedora-list mailing list fedora-list@xxxxxxxxxx To unsubscribe: https://www.redhat.com/mailman/listinfo/fedora-list Guidelines: http://fedoraproject.org/wiki/Communicate/MailingListGuidelines
