[Date Index]
[Thread Index]
[Author Index]
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?**
| |