MathGroup Archive 2003

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

Search the Archive

RE: RE: Re: Is Sort stable?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg39801] RE: [mg39754] RE: [mg39743] Re: [mg39725] Is Sort stable?
  • From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
  • Date: Fri, 7 Mar 2003 03:40:57 -0500 (EST)
  • Sender: owner-wri-mathgroup at wolfram.com

>-----Original Message-----
>From: Dr Bob [mailto:drbob at bigfoot.com]
To: mathgroup at smc.vnet.net
>Sent: Thursday, March 06, 2003 4:03 PM
>To: Wolf, Hartmut; mathgroup at smc.vnet.net
>Subject: [mg39801] Re: [mg39754] RE: [mg39743] Re: [mg39725] Is Sort stable?
>
>
>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
>

Well, Bobby, that's the observation. The question is, from where do we know?
See e.g., a well-known sort algorithm:
 
In[108]:= ClearAll[qsort];
In[109]:= Attributes[qsort] = HoldFirst;

In[110]:=
qsort[a_Symbol, l_Integer, r_Integer, compare_] := 
  If[r > l, Block[{v = a[[r]], i = l - 1, j = r}, 
      While[True,
        While[i < r && compare[a[[++i]], v]];
        While[j > l && ! compare[a[[--j]], v]];
        If[i >= j, Break[]];
        a[[{i, j}]] = a[[{j, i}]];];
      a[[{i, r}]] = a[[{r, i}]];
      qsort[a, l, i - 1, compare];
      qsort[a, i + 1, r, compare];]]

In[111]:=
qsort[a_Symbol, compare_] := qsort[a, 1, Length[a], compare]
 


 
In[119]:= s = s0 =
    Table[{Random[Integer, {1, 3}], Random[Integer, {1, 10}]}, {30}]
Out[119]=
{{2, 5}, {2, 2}, {2, 6}, {3, 7}, {1, 10}, {2, 5}, {3, 10}, {2, 4}, {3, 2},
{3,
     7}, {1, 1}, {3, 6}, {3, 8}, {3, 1}, {3, 6}, {1, 2}, {2, 7}, {3, 2}, {3,

    1}, {2, 8}, {2, 9}, {3, 5}, {3, 10}, {1, 9}, {3, 3}, {1, 1}, {3, 7}, {2,

    5}, {1, 7}, {1, 9}}

In[120]:= qsort[s, First[#1] <= First[#2] &]
In[121]:= s
Out[121]=
{{1, 7}, {1, 1}, {1, 9}, {1, 2}, {1, 10}, {1, 1}, {1, 9}, {2, 4}, {2, 5},
{2, 
    2}, {2, 5}, {2, 6}, {2, 9}, {2, 8}, {2, 7}, {2, 5}, {3, 6}, {3, 2}, {3, 
    1}, {3, 1}, {3, 8}, {3, 5}, {3, 10}, {3, 6}, {3, 3}, {3, 7}, {3, 7}, {3,

    2}, {3, 7}, {3, 10}}

In[122]:= s = s0;
In[123]:= qsort[s, First[#1] < First[#2] &]
In[124]:= s
Out[124]=
{{1, 9}, {1, 1}, {1, 7}, {1, 1}, {1, 9}, {1, 10}, {1, 2}, {2, 5}, {2, 4},
{2, 
    5}, {2, 2}, {2, 5}, {2, 6}, {2, 9}, {2, 8}, {2, 7}, {3, 2}, {3, 6}, {3, 
    2}, {3, 1}, {3, 1}, {3, 8}, {3, 5}, {3, 10}, {3, 7}, {3, 3}, {3, 6}, {3,

    7}, {3, 10}, {3, 7}}

In[125]:= qsort[s, First[#1] < First[#2] &]
In[126]:= s
Out[126]= 
{{1, 2}, {1, 9}, {1, 1}, {1, 7}, {1, 1}, {1, 9}, {1, 10}, {2, 7}, {2, 5},
{2, 
    4}, {2, 5}, {2, 2}, {2, 5}, {2, 6}, {2, 9}, {2, 8}, {3, 7}, {3, 2}, {3, 
    6}, {3, 2}, {3, 1}, {3, 1}, {3, 8}, {3, 5}, {3, 10}, {3, 7}, {3, 3}, {3,

    6}, {3, 7}, {3, 10}}

You see, this one behaves different! In the second case with comparison
function Less, even a sorted input (sorted by the very same function) isn't
stable!


However try:

ss = Transpose[{s0[[All, 1]], Range[Length[s0]], s0[[All, -1]]}];
qsort[ss, Order[##] === 1 &];
ss[[All, {1, -1}]]



--
Hartmut Wolf



>On Thu, 6 Mar 2003 02:35:07 -0500 (EST), Wolf, Hartmut 
><Hartmut.Wolf@t- 
>systems.com> wrote:
>
>>
[...]

>>
>> I wonder, wether this is an asserted property of Sort. Couldn't find
>> anything concerning that in the documentation.
>>
>>
[...]



  • Prev by Date: Re: Functional differentiation on lattice
  • Next by Date: Re: RE: Re: Is Sort stable?
  • Previous by thread: Re: Re: Is Sort stable?
  • Next by thread: Re: RE: Re: Is Sort stable?