RE: Re: Is Sort stable?
- To: mathgroup at smc.vnet.net
- Subject: [mg39754] RE: [mg39743] Re: [mg39725] Is Sort stable?
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Thu, 6 Mar 2003 02:35:07 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
>-----Original Message----- >From: BobHanlon at aol.com [mailto:BobHanlon at aol.com] To: mathgroup at smc.vnet.net >Sent: Wednesday, March 05, 2003 6:05 AM >To: mathgroup at smc.vnet.net >Subject: [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
- Follow-Ups:
- Re: RE: Re: Is Sort stable?
- From: Dr Bob <drbob@bigfoot.com>
- Re: RE: Re: Is Sort stable?