@arpit : why algo subtracts 1 from each number of the input? On Sun, May 6, 2012 at 12:02 AM, Arpit Gupta <arpitgupta.211...@gmail.com>wrote:
> 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. > -- 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.
