MathGroup Archive 1992

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

Search the Archive

Re: Sorting and "ordering functions"

  • To: mathgroup at yoda.physics.unc.edu
  • Subject: Re: Sorting and "ordering functions"
  • From: keiper
  • Date: Tue, 8 Dec 92 10:03:22 CST

JWENDEL at isdmnl.wr.usgs.gov writes:
    > The main question suggested is: what is an ordering function
    > p as cited on pg 870 of the Mma book; can it be any function of
    > two variables, or must it have properties such as transitivity
    > (x<y and x<z -> x<z) and non-reflexivity (x<x is False)? 

Non-reflexivity is not an issue, but unless transitivity is assumed, any
sorting algorithm will be O(n^2): you simply have to compare all pairs.
This is simply unacceptable when any respectable sorting algorithm is
O(n log(n)).  Because transitivity is assumed (verifying that it is would
be silly) you will get unpredictable results if it is in fact not transitive.

Just for the record, the sort used is a merge sort.  The reason is that
even in the worst case few comparisons are needed.

Jerry B. Keiper
keiper at wri.com





  • Prev by Date: Re: Difference equations
  • Next by Date: Mathematica and Q'Nial
  • Previous by thread: Re: PointSize in ListPlot
  • Next by thread: Mathematica and Q'Nial