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. >> >> [...]