Re: RE: Re: Is Sort stable?
- To: mathgroup at smc.vnet.net
- Subject: [mg39793] Re: [mg39754] RE: [mg39743] Re: [mg39725] Is Sort stable?
- From: Dr Bob <drbob at bigfoot.com>
- Date: Fri, 7 Mar 2003 03:39:20 -0500 (EST)
- References: <200303060735.CAA09188@smc.vnet.net>
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
There's nothing mysterious going on. Sort reverses the order of elements when the ordering function evaluates to False. If the ordering function is False in case of equality --- as in #1 < #2& --- then order will be reversed within "groups", exactly as we should expect. Bobby On Thu, 6 Mar 2003 02:35:07 -0500 (EST), Wolf, Hartmut <Hartmut.Wolf@t- systems.com> wrote: > >> -----Original Message----- >> From: BobHanlon at aol.com [mailto:BobHanlon at aol.com] To: mathgroup at smc.vnet.net > To: mathgroup at smc.vnet.net >> Sent: Wednesday, March 05, 2003 6:05 AM >> To: mathgroup at smc.vnet.net >> Subject: [mg39793] [mg39754] [mg39743] Re: [mg39725] Is Sort stable? >> >> >> >> In a message dated 3/4/03 1:25:41 AM, rolle at ifm.liu.se writes: >> >> >>> --Short form: >>> Is the sorting algorithm implemented by Sort[] stable? >>> >>> --Long form: >>> I'm doing a thingy where I need to take out subsets of data >> and look at >>> them >>> individually. I have a labeled data set, with labels being a >> vector of 1,2 >>> ... denoting class membership, and I've tried to pick out >> subset using >>> either e.g. >>> >>> Extract[data, Position[labels,1]] >>> => the data points in "class 1" >>> >>> or using Sort to sort data according to labels (so I get >> e.g. {1,1,1,1, ... >>> 2,2,2, ... 3,3,3}, and which is nice for plotting data sets. >> This work ok, >>> but it seems like Sort[] is rearranging the data points >> within classes >>> different from Extract[]. Does anyone know i Is the Sort[] algorithm >>> stable? >>> Could there be something else lurking here? >>> >>> >> >> data = Table[ >> >> {Random[Integer,{1,3}],Random[Integer,{1,3}],Random[]}, >> >> {20}] >> >> >> >> The default is a multi-position sort >> >> >> >> Sort[data] >> >> >> >> Sorting solely by the first position reverses the order of the elements >> within the individual groupings >> >> >> >> Sort[data, #1[[1]]<#2[[1]]&] >> >> >> >> To use Sort and leave the order within groupings untouched >> >> >> >> Sort[Reverse[data], #1[[1]]<#2[[1]]&] >> >> >> >> Verifying, >> >> >> >> %==Flatten[Table[ >> >> Extract[data,Position[data,{n,_,_}]], >> >> {n,3}], 1] >> >> >> or alternatively >> >> %%==Flatten[Table[ >> >> Cases[data, {n,_,_}], {n,3}],1] >> >> >> >> Bob Hanlon >> >> >> > > Dear Bob, > > this is a very interesting observation. I conform it testing in addition > for > symbols (without value), strings and Complex payload, but I didn't check > for > more intricate expressions. Although this behaviour can be read off my > first > reply, I didn't see it, "having tomatoes on my eyes". > > I wonder, wether this is an asserted property of Sort. Couldn't find > anything concerning that in the documentation. > > > When the size of the problem is large, however, I'd recommend my method, > being more performant (and not relying on the implementation), e.g.: > > In[229]:= size = 30000; > In[230]:= s = Table[{Random[Integer, {1, 3}], Random[Integer, {1, > size}]}, {size}]; > > In[231]:= > s[[Ordering[Transpose[{s[[All, 1]], Range[Length[s]]}]] ]]; // Timing > Out[231]= {0.08 Second, Null} > > In[232]:= Sort[Reverse[s], First[#1] < First[#2] &]; // Timing > Out[232]= {7.16 Second, Null} > > -- > Hartmut > > > -- majort at cox-internet.com Bobby R. Treat
- References:
- RE: Re: Is Sort stable?
- From: "Wolf, Hartmut" <Hartmut.Wolf@t-systems.com>
- RE: Re: Is Sort stable?