Re: Re: Is Sort stable?

*To*: mathgroup at smc.vnet.net*Subject*: [mg39756] Re: [mg39743] Re: [mg39725] Is Sort stable?*From*: BobHanlon at aol.com*Date*: Thu, 6 Mar 2003 02:35:14 -0500 (EST)*Sender*: owner-wri-mathgroup at wolfram.com

In a message dated 3/5/03 6:40:32 AM, Hartmut.Wolf at t-systems.com writes: > > >-----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: [mg39756] [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 > > > Hartmut, I just noticed that with Sort the ordering within the groups is not reversed if you include equality in the Sort criteria, i.e., Sort[s, First[#1] <= First[#2] &] In any event your Ordering method is far superior. Bob Hanlon