3 pointers
temp0 = first non 0 from start
temp2 = first non 2 from end
temp1 = temp0
loop till temp1 < temp2
if temp1 ==0
swap a[temp1] a[temp0]
temp0++
if temp1 == 2
swap a[temp1] a[temp2]
temp2--
if temp1==1
temp1++
end
On Fri, Jul 2, 2010 at 8:16 AM, Gene <[email protected]> wrote:
> On Jul 1, 4:04 pm, jalaj jaiswal <[email protected]> wrote:
> > i was talking about the space complexity.. running time is obvs O(n)
>
> Hello J.J.
>
> Why would those 3 lines of executable code you cited say anything
> about space complexity? They don't allocate memory. You must be
> quibbling.
>
> There's no issue with space either. Whatever space the lookup table
> takes is O(M) where M is the number of distinct symbols. But if you
> didn't have the table, you'd need a chain of "if"s or a switch (as the
> other posted solutions use), which compile to code that's O(M) in
> size. It's a wash.
>
> Finally, if the number of symbols M were large, you could use a O(1)
> time lookup scheme like a perfect hash to avoid the O(M) factor of
> runtime for the linear lookup.
>
> Cheers.
>
> > On Thu, Jul 1, 2010 at 9:14 PM, Gene <[email protected]> wrote:
> > > On Jun 30, 3:38 am, Debajyoti Sarma <[email protected]> wrote:
> > > > @Gene
> > > > your code's last 3 line gives doubt.
> > > > .......
> > > > for (i = j = 0; j < M; j++)
> > > > while (c[j]--)
> > > > a[i++] = j;
> > > > .......
> > > > Is it don't make the complexity more than O(n) ??
> >
> > > Not at all. The inner loop body executes n times no matter what the
> > > value of M is.
> >
> > > Guys, this is just a special case of counting sort. Obviously O(n).
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected]<algogeeks%[email protected]>
> <algogeeks%2bunsubscr...@googlegroups .com>
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > With Regards,
> > Jalaj Jaiswal
> > +919026283397
> > B.TECH IT
> > IIIT ALLAHABAD
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
