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