Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2003
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2003

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

Search the Archive

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



  • Prev by Date: Re: Is Sort stable?
  • Next by Date: Re: Solving a system of Inequalities
  • Previous by thread: Re: Is Sort stable?
  • Next by thread: Re: Re: Is Sort stable?