Read the problem for constraints.... Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com
On Tue, May 8, 2012 at 11:12 AM, Mahesh Thakur <tmahesh...@gmail.com> wrote: > I think if range is till n2, max passes for radix sort will be 3. > by subtracting 1 to all the numbers we get the max range to n2-1 and radix > sort can be done in 2 passes. > but what will happen when if we have a '0' in array and then we subtract 1 > to it? > > > On Tue, May 8, 2012 at 9:48 AM, atul anand <atul.87fri...@gmail.com>wrote: > >> @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. >> > > -- > 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.
