MathGroup Archive 2003

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

Search the Archive

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


  • Prev by Date: RE: Re: Is Sort stable?
  • Next by Date: Problem for exponent and indice
  • Previous by thread: Re: RE: Re: Is Sort stable?
  • Next by thread: Re: Is Sort stable?