in-place is O(1) auxiliary space. Could you please of something else? On Thursday, 5 April 2012 10:24:09 UTC+5:30, Rujin Cao wrote: > > =?utf-8?Q?_bit_integers,_sort_them_in-place_in_O(n)_time?= > MIME-Version: 1.0 > Content-Type: multipart/alternative; > boundary="----=_Part_1591_7508851.1333541114758" > > ------=_Part_1591_7508851.1333541114758 > Content-Type: text/plain; charset="utf-8" > Content-Transfer-Encoding: quoted-printable > > using counting sort with an extra O(log n) space to store the > appearance count of each number in the range[0,log n]. > And then iterate from begin to end to set each number with its count > times. > I'm not sure whether it is appropriate to call it "in-place", but at > least it doesn't use O(n) space. > > Sent from my Windows Phone > =E5=8F=91=E4=BB=B6=E4=BA=BA: Doom > =E5=8F=91=E9=80=81=E6=97=B6=E9=97=B4: 2012/4/4 20:05 > =E6=94=B6=E4=BB=B6=E4=BA=BA: algogeeks@googlegroups.com > =E4=B8=BB=E9=A2=98: Re: [algogeeks] Given an array A[1..n] of log n bit > int= > egers, > sort them in-place in O(n) time > how are you going to do it "in-place"? > > On Wednesday, 4 April 2012 13:24:01 UTC+5:30, Siddhartha wrote: > > > > if the length of the binary representation of elements is logn, then the= > =20 > > elements themselves are of size less than 2^log(n)=3Dn. > > as all the elements are less than n, use counting sort!!! > > > > --=20 > 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/al= > gogeeks/-/glXPUeyoh8IJ. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscribe@googleg= > roups.com. > For more options, visit this group at > http://groups.google.com/group/algoge= > eks?hl=3Den. > > > ------=_Part_1591_7508851.1333541114758 > Content-Type: text/html; charset="utf-8" > Content-Transfer-Encoding: quoted-printable > > <html><head><meta content=3D"text/html; charset=3Dutf-8" > http-equiv=3D"Cont= > ent-Type"></head><body><div><div style=3D"font-family: Calibri,sans-serif; > = > font-size: 11pt;">using counting sort with an extra O(log n) space to > store= > the appearance count of each number in the range[0,log n].<br>And then > ite= > rate from begin to end to set each number with its count times.<br>I'm not > = > sure whether it is appropriate to call it "in-place", but at least it > doesn= > 't use O(n) space.<br><br>Sent from my Windows > Phone<br></div></div><hr><sp= > an style=3D"font-family: Tahoma,sans-serif; font-size: 10pt; font-weight: > b= > old;">=E5=8F=91=E4=BB=B6=E4=BA=BA: </span><span style=3D"font-family: > Tahom= > a,sans-serif; font-size: 10pt;">Doom</span><br><span style=3D"font-family: > = > Tahoma,sans-serif; font-size: 10pt; font-weight: bold;">=E5=8F=91=E9=80=81= > =E6=97=B6=E9=97=B4: </span><span style=3D"font-family: Tahoma,sans-serif; > f= > ont-size: 10pt;">2012/4/4 20:05</span><br><span style=3D"font-family: > Tahom= > a,sans-serif; font-size: 10pt; font-weight: > bold;">=E6=94=B6=E4=BB=B6=E4=BA= > =BA: </span><span style=3D"font-family: Tahoma,sans-serif; font-size: > 10pt;= > ">algogeeks@googlegroups.com</span><br><span style=3D"font-family: > Tahoma,s= > ans-serif; font-size: 10pt; font-weight: bold;">=E4=B8=BB=E9=A2=98: > </span>= > <span style=3D"font-family: Tahoma,sans-serif; font-size: 10pt;">Re: > [algog= > eeks] Given an array A[1..n] of log n bit integers, sort them in-place in > O= > (n) time</span><br><br></body></html>how are you going to do it > "in-place"?= > <br><br>On Wednesday, 4 April 2012 13:24:01 UTC+5:30, Siddhartha > wrote:<bl= > ockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: > 0.8ex;border= > -left: 1px #ccc solid;padding-left: 1ex;">if the length of the binary > repre= > sentation of elements is logn, then the elements themselves are of size > les= > s than 2^log(n)=3Dn.<div>as all the elements are less than n, use counting > = > sort!!!</div> > </blockquote> > > <p></p> > > -- <br /> > You received this message because you are subscribed to the Google Groups > "= > Algorithm Geeks" group.<br /> > To view this discussion on the web visit <a href=3D" > https://groups.google.c= > om/d/msg/algogeeks/-/glXPUeyoh8IJ"> > https://groups.google.com/d/msg/algogeek= > s/-/glXPUeyoh8IJ</a>.<br />=20 > To post to this group, send email to algogeeks@googlegroups.com.<br /> > To unsubscribe from this group, send email to > algogeeks+unsubscribe@googleg= > roups.com.<br /> > > For more options, visit this group at > http://groups.google.com/group/algoge= > eks?hl=3Den.<br /> > > ------=_Part_1591_7508851.1333541114758-- > >
-- 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/-/LGcbPhxQFrsJ. 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.
