Re: Is Sort stable?
- To: mathgroup at smc.vnet.net
- Subject: [mg39773] Re: Is Sort stable?
- From: Paul Abbott <paul at physics.uwa.edu.au>
- Date: Fri, 7 Mar 2003 03:30:17 -0500 (EST)
- Organization: The University of Western Australia
- References: <b41bv1$pea$1@smc.vnet.net> <b440eu$165$1@smc.vnet.net> <b46u2m$924$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
In article <b46u2m$924$1 at smc.vnet.net>,
"Roland Nilsson" <rolle at ifm.liu.se> wrote:
> 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 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.
It is interesting to use Trace to try to see what is happening here:
data = {{1, 4}, {1, 2}, {3, 4}, {2, 3}};
Trace[Sort[data, #1[[1]] < #2[[1]] & ]] // TableForm
Trace[Sort[data, #1[[1]] <= #2[[1]] & ]] // TableForm
Cheers,
Paul
--
Paul Abbott Phone: +61 8 9380 2734
School of Physics, M013 Fax: +61 8 9380 1014
The University of Western Australia (CRICOS Provider No 00126G)
35 Stirling Highway
Crawley WA 6009 mailto:paul at physics.uwa.edu.au
AUSTRALIA http://physics.uwa.edu.au/~paul