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.
