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