Re: RE: Re: Is Sort stable?
- To: mathgroup at smc.vnet.net
- Subject: [mg39804] Re: [mg39754] RE: [mg39743] Re: [mg39725] Is Sort stable?
- From: Dr Bob <drbob at bigfoot.com>
- Date: Fri, 7 Mar 2003 03:41:49 -0500 (EST)
- References: <8EB1C3634596D6118952006008F711CD5BCD15@debis.com>
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
Maybe I misunderstand you, but I think you showed that your qsort function
doesn't preserve order for "ties" --- cases of equality in the comparison
function. That doesn't surprise me at all. Sort uses the original list
position of each element as the tie-breaker, as you've also shown. The
following always gives True:
s0 = Table[{Random[Integer, {1, 3}], Random[Integer, {1, 10}]}, {30}];
ss = Transpose[{s0[[All, 1]], Range[Length[s0]], s0[[All, -1]]}];
qsort[ss, #1[[1]] < #2[[1]] || (#1[[1]] == #2[[1]] && #1[[2]] â?¤ #2[[2]])
&];
ss[[All, {1, -1}]];
Sort[s0, #1[[1]] â?¤ #2[[1]] &][[All, {1, -1}]];
% == %%
True
Efficient sorts don't normally do that --- but it's actually a very
desirable property.
It certainly should be DOCUMENTED, though!
Bobby
On Thu, 6 Mar 2003 18:27:21 +0100, Wolf, Hartmut <Hartmut.Wolf@t-
systems.com> wrote:
>
>> -----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: [mg39804] 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.
>>>
>>>
> [...]
>
>
--
majort at cox-internet.com
Bobby R. Treat