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?