Hi guys, 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) . Can someone please give me a hint. Would be very very thankful! Thanks in advance! D.
Ignacio Vazquez-Abrams
2008-Dec-13 18:51 UTC
[CentOS] [OT] stable algorithm with complexity O(n)
On Sat, 2008-12-13 at 19:24 +0100, David Hl??ik wrote:> Hi guys, > > 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) . > > Can someone please give me a hint. Would be very very thankful!Merge sort? Insertion sort? Selection sort? timsort? -- Ignacio Vazquez-Abrams <ivazqueznet at gmail.com> PLEASE don't CC me; I'm already subscribed -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 197 bytes Desc: This is a digitally signed message part URL: <http://lists.centos.org/pipermail/centos/attachments/20081213/803e67bb/attachment-0003.sig>
Well, something with linear complexity O(n) which i have to prove, Merge sort, Insertion sort or selection sort does not have O(n) complexity. I believe that something like RadixSort, CountingSort, BucketSort altought i am not sure Thanks! D. On Sat, Dec 13, 2008 at 7:51 PM, Ignacio Vazquez-Abrams <ivazqueznet at gmail.com> wrote:> On Sat, 2008-12-13 at 19:24 +0100, David Hl??ik wrote: >> Hi guys, >> >> 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) . >> >> Can someone please give me a hint. Would be very very thankful! > > Merge sort? Insertion sort? Selection sort? timsort? > > -- > Ignacio Vazquez-Abrams <ivazqueznet at gmail.com> > > PLEASE don't CC me; I'm already subscribed > > _______________________________________________ > CentOS mailing list > CentOS at centos.org > http://lists.centos.org/mailman/listinfo/centos > >
NiftyClusters T Mitchell
2008-Dec-17 08:17 UTC
[CentOS] [OT] stable algorithm with complexity O(n)
On Sat, Dec 13, 2008 at 10:24 AM, David Hl??ik <david at hlacik.eu> wrote:> Hi guys, > > 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) . > > Can someone please give me a hint. Would be very very thankful!Knuth. Art of Computer Programming Volume 3: Sorting and Searching (2nd Edition) by Donald E. Knuth -- NiftyCluster T o m M i t c h e l l