Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>