MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Is Sort stable?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg39789] Re: [mg39755] Re: Is Sort stable?
  • From: Dr Bob <drbob at bigfoot.com>
  • Date: Fri, 7 Mar 2003 03:38:24 -0500 (EST)
  • References: <b41bv1$pea$1@smc.vnet.net> <b440eu$165$1@smc.vnet.net> <200303060735.CAA09193@smc.vnet.net>
  • Reply-to: drbob at bigfoot.com
  • Sender: owner-wri-mathgroup at wolfram.com

The Sort function preserves the existing order of two elements when the 
ordering function's value is True.  It reverses the order of elements for 
which the ordering function is False.  For instance, with your example:

{{1, 2}, {2, 3}, {1, 4}, {3, 4}};
Sort[%, #1[[1]] < #2[[1]] &]
Sort[%%, #1[[1]] â?¤ #2[[1]] &]

{{1,4},{1,2},{2,3},{3,4}}
{{1,2},{1,4},{2,3},{3,4}}

In both cases, elements were reversed only if the ordering function was 
False.  The default ordering function, OrderQ, is true in case of equality, 
so the default Sort is "stable".

Properly understood, Sort is always stable.

Bobby

On Thu, 6 Mar 2003 02:35:11 -0500 (EST), Roland Nilsson <rolle at ifm.liu.se> 
wrote:

>>
>> a sorting algorithm can't be unstable !
>> Mathematica probably do a quick sort algorithm.
>
> I think there was some terminology confusion here. Sorting algorithms are
> referred to as "stable" (in my world at least) when elements that are 
> *not*
> different with respect to the order are guaranteed *not to be 
> rearranged*.
> I.e., sorting the list
>
> (1, 2)
> (2, 3)
> (1, 4)
> (3 ,4)
>
> w.r.t. the first column only will always yield
>
> (1, 2)
> (1, 4)
> (2, 3)
> (3 ,4)
>
> with a *stable* sort algorithm. Unstable sorting
> maykuska at informatik.uni-leipzig.de <kuska at informatik.uni-leipzig.de>
> rearrange (1,2) and (1,4) at will.
> It seems to me from the discussion in this thread that Mathematica's Sort
> does reverse such elements.
>
> /Roland
>
>
>
>
>



-- 
majort at cox-internet.com
Bobby R. Treat



  • Prev by Date: Re: Functional differentiation on lattice
  • Next by Date: Re: Mathlink problem with binary.tm in Linux
  • Previous by thread: Re: Is Sort stable?
  • Next by thread: RE: RE: Re: Is Sort stable?