@Mohit: As I said, a radix sort does not use data comparisons. It
extracts "digits" from the sort keys and uses the digits as
subscripts. Other than moving the data around, this is the only use
the radix sort makes of the sort keys.
Dave
On Aug 31, 11:06 am, mohit verma <mohit89m...@gmail.com> wrote:
> Is anything specific about digits of numbers given in above question? If no
> then as i said....
> Yeah coz we compare the radix part in radix sort , so can't say exactly we
> are comparing the numbers (but portion of it)
>
>
>
>
>
> On Wed, Aug 31, 2011 at 9:27 PM, Dave <dave_and_da...@juno.com> wrote:
> > @Mohit: No. Radix sort on a fixed data type is O(n) in time, and uses
> > no data comparisons.
>
> > Dave
>
> > On Aug 31, 10:45 am, mohit verma <mohit89m...@gmail.com> wrote:
> > > @ dave- commplexity of radix sort is >= O(n log n). so better use heap
> > sort.
>
> > > On Wed, Aug 31, 2011 at 4:07 PM, Dave <dave_and_da...@juno.com> wrote:
> > > > @Bharatkumar: You've tacitly assumed that the data values are in the
> > > > range 0 to n-1. That's not given in the problem statement.
>
> > > > Dave
>
> > > > On Aug 31, 1:16 am, bharatkumar bagana <bagana.bharatku...@gmail.com>
> > > > wrote:
> > > > > bitset <n> duplicates;// n- bit space..
> > > > > for(int i=0;i<n;i++)
> > > > > {
> > > > > if(duplicates[array[i]] ==1)
> > > > > print duplicate...
> > > > > else duplicate[array[i]]=1;}
>
> > > > > there is no comparison between any 2 numbers ....O(n) time .....space
> > is
> > > > > O(n)bits ...
>
> > > > > On Tue, Aug 30, 2011 at 5:18 PM, Dave <dave_and_da...@juno.com>
> > wrote:
> > > > > > Replying to myself... A radix sort takes O(n) extra space.
>
> > > > > > Dave
>
> > > > > > On Aug 30, 1:49 pm, Dave <dave_and_da...@juno.com> wrote:
> > > > > > > @Kamakshii: With O(1) extra space, it can be done with O(n)
> > > > > > > comparisons. Do a radix sort on the input (no comparisons), and
> > then
> > > > > > > check adjacent numbers for equality.
>
> > > > > > > Dave
>
> > > > > > > On Aug 30, 1:34 pm, Kamakshii Aggarwal <kamakshi...@gmail.com>
> > > > wrote:
>
> > > > > > > > develop an algorithm to find duplicates in a list of numbers
> > > > without
> > > > > > using a
> > > > > > > > binary tree..if there are n distinct numbers in the list ,how
> > many
> > > > > > times
> > > > > > > > must two numbers be compared for equality in your
> > algorithm?what if
> > > > all
> > > > > > > > numbers are equal?
>
> > > > > > > > --
> > > > > > > > Regards,
> > > > > > > > Kamakshi
> > > > > > > > kamakshi...@gmail.com- Hide quoted text -
>
> > > > > > > - Show quoted text -
>
> > > > > > --
> > > > > > 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.
>
> > > > > --
>
> > > > > **Please do not print this e-mail until urgent requirement. Go
> > Green!!
> > > > > Save Papers <=> Save Trees
> > > > > *BharatKumar Bagana*
> > > > > **http://www.google.com/profiles/bagana.bharatkumar<
> > > >http://www.google.com/profiles/bagana.bharatkumar>
> > > > > *
> > > > > Mobile +91 8056127652*
> > > > > <bagana.bharatku...@gmail.com>- Hide quoted text -
>
> > > > > - Show quoted text -
>
> > > > --
> > > > 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.
>
> > > --
> > > ........................
> > > *MOHIT VERMA*- Hide quoted text -
>
> > > - Show quoted text -
>
> > --
> > 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.
>
> --
> ........................
> *MOHIT VERMA*- Hide quoted text -
>
> - Show quoted text -
--
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.
