1) Substract 1 from each no. 2) Now after substracting 1 from each no, convert it to base n. for example for n=6,the number 36 will be converted to 55. (36-1=35 and 35 when converted to base 6 is 55) 3) Thus all the nos in the range 1 to 6^2 can be mapped to numbers between 00 to 55. 4) Now apply radix sort(for two digits) for the mapped values. 5)After sorting the mapped values convert base n values to decimal and add 1.
This is o(n) algo. PS: I am not the designer of this algo. One of my seniors told me. On Sat, May 5, 2012 at 2:42 PM, saurabh singh <saurab...@gmail.com> wrote: > I think I couldn't make myself clear... > This line in your algorithm "*After this just iterate through the aux > array printing the index aux[i] times.*" > this makes your algorithm O(n^2) since the size of aux is n^2 and in the > worst case the complete traversal of aux may be required. > > Saurabh Singh > B.Tech (Computer Science) > MNNIT > blog:geekinessthecoolway.blogspot.com > > > > On Sat, May 5, 2012 at 2:37 PM, Jeevitesh <jeeviteshshekha...@gmail.com>wrote: > >> Hi Shiva. >> >> You are right we will be wasting a lot of memory. >> But still it depends like if we have lot of numbers in the range of 1, >> n^2 present in the input array then this trade off is not bad. >> The issue here is we cannot otherwise sort it in O(n) time unless and >> until we have extra space. >> >> So we will have to live with it in this case as i do not think it would >> be possible in O(n) time otherwise. >> >> >> On Sat, May 5, 2012 at 2:33 PM, shiv narayan >> <narayan.shiv...@gmail.com>wrote: >> >>> @jeevitesh yeah that may be right but it requires extra space as lot >>> of space will be wasted... >>> >>> On May 5, 1:44 pm, Jeevitesh <jeeviteshshekha...@gmail.com> wrote: >>> > Hi all, >>> > >>> > I am new to this group. >>> > >>> > My last post was deleted i do not know the reason behind it. >>> > >>> > I will explain my logic here:- >>> > >>> > as the range is 1 to n^2 we have a input array like input[n^2]. >>> > We can take a auxillary array of size n^2 like aux[n^2]. >>> > Scan the input array. >>> > For each input input[i] increment by one corresponding aux[input[i]]. >>> > After this just iterate through the aux array printing the index aux[i] >>> > times. >>> > >>> > This way we can sort it in O(n) time. >>> > >>> > >>> > >>> > >>> > >>> > >>> > >>> > >>> > >>> > On Sat, May 5, 2012 at 2:02 PM, saurabh singh <saurab...@gmail.com> >>> wrote: >>> > > After giving some thought,I think even radix sort may not be >>> sufficient. >>> > > Complexity of radix sort is O(k*n) where k is the number of buckets >>> > > required to sort the given range. >>> > > The number of buckets is proportional to the number of bits required >>> to >>> > > represent the *maximum number in the given range.*For our case the >>> > > maximum number is O(n^2).Hence *the number of buckets required would >>> be >>> > > proportional to log(n^2) in the worst case.* >>> > > Hence the worst case complexity for the given constraints using >>> radix sort >>> > > would be *O(n*(log n^2)) = O(n*logn).* >>> > > This is no better than comparision sort.A slight optimization that >>> we can >>> > > make is to use a higher base which would reduce the number of buckets >>> > > required but would add the cost of converting each number into the >>> higher >>> > > base. >>> > > Somehow I am getting convinced worst case O(n) algorithm may not be >>> > > possible.Working on the mathematical proof. >>> > >>> > > Saurabh Singh >>> > > B.Tech (Computer Science) >>> > > MNNIT >>> > > blog:geekinessthecoolway.blogspot.com >>> > >>> > > On Sat, May 5, 2012 at 8:37 AM, saurabh singh <saurab...@gmail.com> >>> wrote: >>> > >>> > >> @cegprakash They are n numbers lying in the range 1 to n^2.Not >>> > >> necessarily sorted. >>> > >> eg 3 4 1 2 5 8 (6 numbers satisfying the conditions given in the >>> problem) >>> > >> Saurabh Singh >>> > >> B.Tech (Computer Science) >>> > >> MNNIT >>> > >> blog:geekinessthecoolway.blogspot.com >>> > >>> > >> On Sat, May 5, 2012 at 5:17 AM, Prakash D <cegprak...@gmail.com> >>> wrote: >>> > >>> > >>> The range 1 to n^2 is already sorted >>> > >>> > >>> On Sat, May 5, 2012 at 12:17 AM, Algobiz < >>> deepak.arulkan...@gmail.com> >>> > >>> wrote: >>> > >>> > How to sort n numbers in the range of 1 to n^2 in O(n).. Any >>> ideas? >>> > >>> > >>> > -- >>> > >>> > You received this message because you are subscribed to the >>> Google >>> > >>> Groups >>> > >>> > "Algorithm Geeks" group. >>> > >>> > To view this discussion on the web visit >>> > >>> >https://groups.google.com/d/msg/algogeeks/-/PGgMdaIbGIsJ. >>> > >>> > To post to this group, send email to algogeeks@googlegroups.com. >>> > >>> > To unsubscribe from this group, send email to >>> > >>> > algogeeks+unsubscr...@googlegroups.com. >>> > >>> > For more options, visit this group at >>> > >>> >http://groups.google.com/group/algogeeks?hl=en. >>> > >>> > >>> -- >>> > >>> You received this message because you are subscribed to the Google >>> > >>> Groups "Algorithm Geeks" group. >>> > >>> To post to this group, send email to algogeeks@googlegroups.com. >>> > >>> To unsubscribe from this group, send email to >>> > >>> algogeeks+unsubscr...@googlegroups.com. >>> > >>> For more options, visit this group at >>> > >>>http://groups.google.com/group/algogeeks?hl=en. >>> > >>> > > -- >>> > > You received this message because you are subscribed to the Google >>> Groups >>> > > "Algorithm Geeks" group. >>> > > To post to this group, send email to algogeeks@googlegroups.com. >>> > > To unsubscribe from this group, send email to >>> > > algogeeks+unsubscr...@googlegroups.com. >>> > > For more options, visit this group at >>> > >http://groups.google.com/group/algogeeks?hl=en. >>> > >>> > -- >>> > *Thanks, >>> > Jeevitesh Shekhar Singh.* >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> To post to this group, send email to algogeeks@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Arpit Gupta B.Tech Third Year Computer Science And Engineering M.N.N.I.T Allahabad arpitgupta.211...@gmail.com -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
