c_cpp/etc/calc/help/sort

   1 NAME
   2     sort - sort a copy of a list or matrix
   3
   4 SYNOPSIS
   5     sort(x)
   6
   7 TYPES
   8     x           list or matrix
   9
  10     return      same type as x
  11
  12 DESCRIPTION
  13     For a list or matrix x, sort(x) returns a list or
  14     matrix y of the same size as x in which the elements
  15     have been sorted into order completely or partly determined by
  16     a user-defined function precedes(a,b), or if this has not been
  17     defined, by a default "precedes" function which for numbers or
  18     strings is as equivalent to (a < b).   More detail on this default
  19     is given below.  For most of the following discussion
  20     it is assumed that calling the function precedes(a,b) does not
  21     change the value of either a or b.
  22
  23     If x is a matrix, the matrix returned by sort(x) has the same
  24     dimension and index limits as x, but for the sorting, x is treated
  25     as a one-dimensional array indexed only by the double- bracket
  26     notation.   Then for both lists and matrices, if x has size n, it
  27     may be identified with the array:
  28
  29                 (x[[0]], x[[1]], ..., x[[n-1]])
  30
  31     which we will here display as:
  32
  33                 (x_0, x_1, ..., x_n-1).
  34
  35     The value y = sort(x) will similarly be identified with:
  36
  37                 (y_0, y_1, ..., x_n-1),
  38
  39     where, for some permutation p() of the integers (0, 1, ..., n-1):
  40
  41                 y_p(i) = x_i.
  42
  43     In the following i1 and i2 will be taken to refer to different
  44     indices for x, and j1 and j2 will denote p(i1) and p(i2).
  45
  46     The algorithm for evaluating y = sort(x) first makes a copy of x;
  47     x remains unchanged, but the copy may be considered as a first
  48     version of y.  Successive values a in this y are read and compared
  49     with earlier values b using the integer-valued function precedes();
  50     if precedes(a,b) is nonzero, which we may consider as "true",
  51     a is "moved" to just before b; if precedes(a,b) is zero, i.e. "false",
  52     a remains after b.  Until the sorting is completed, other similar
  53     pairs (a,b) are compared and if and only if precedes(a,b) is true,
  54     a is moved to before b or b is moved to after a.  We may
  55     say that the intention of precedes(a,b) being nonzero is that a should
  56     precede b, while precedes(a,b) being zero intends that the order
  57     of a and b is to be as in the original x.  For any integer-valued
  58     precedes() function, the algorithm will return a result for sort(x),
  59     but to guarantee fulfilment of the intentions just described,
  60     precedes() should satisfy the conditions:
  61
  62     (1) For all a, b, c, precedes(a,b) implies precedes(a,c) || precedes (c,b),
  63
  64     (2) For all a, b, precedes(a,b) implies !precedes(b,a).
  65
  66     Condition (1) is equivalent to transitivity of !precedes():
  67
  68     (1)' For all a,b,c, !precedes(a,b) && !precedes(b,c) implies !precedes(a,c).
  69
  70     (1) and (2) together imply transitivity of precedes():
  71
  72     (3) For all a,b,c, precedes(a,b) && precedes(b,c) implies precedes(a,c).
  73
  74     Condition (2) expresses the obvious fact that if a and b are distinct
  75     values in x, there is no permutation in which every occurrence of
  76     a both precedes and follows every occurrence of b.
  77
  78     Condition (1) indicates that if a, b, c occur
  79     in the order  b c a, moving a to before b or b to after a must change
  80     the order of either a and c or c and b.
  81
  82     Conditions (2) and (3) together are not sufficient to ensure a
  83     result satisfying the intentions of nonzero and zero values of
  84     precedes() as described above.  For example, consider:
  85
  86                 precedes(a,b) = a is a proper divisor of b,
  87
  88     and x = list(4, 3, 2).  The only pair for which precedes(a,b) is
  89     nonzero is (2,4),  but x cannot be rearranged so that 2 is before
  90     4 without changing the order of one of the pairs (4,3) and (3,2).
  91
  92     If precedes() does not satisfy the antisymmetry condition (2),
  93     i.e. there exist a, b for which both precedes(a, b)
  94     and precedes(b, a), and if x_i1 = a, x_i2 = b, whether or
  95     not y_j1 precedes or follows y_j2 will be determined by the
  96     sorting algorithm by methods that are difficult to describe;
  97     such a situation may be acceptable to a user not concerned with
  98     the order of occurrences of a and b in the result.  To permit
  99     this, we may now describe the role of precedes(a,b) by the rules:
 100
 101         precedes(a,b) && !precedes(b,a):  a is to precede b;
 102
 103         !precedes(a,b) && !precedes(b,a):  order of a and b not to be changed;
 104
 105         precedes(a,b) && precedes(b,a):  order of a and b may be changed.
 106
 107     Under the condition (1), the result of sort(x) will accord with these rules.
 108
 109     Default precedes():
 110
 111         If precedes(a,b) has not been defined by a define command,
 112         the effect is as if precedes(a,b) were determined by:
 113
 114         If a and b are are not of the same type, they are ordered by
 115
 116                 null values < numbers < strings < objects.
 117
 118         If a and b are of the same type, this type being
 119         null, numbers or strings, precedes(a,b) is given by (a < b).
 120         (If a and b are both null, they are considered to be equal, so
 121         a < b then returns zero.)  For null values, numbers and
 122         strings, this definition has the properties (1) and (2)
 123         discussed above.
 124
 125         If a and b are both xx-objects, a < b is defined to mean
 126         xx_rel(a,b) < 0; such a definition does not
 127         necessarily give < the properties usually expected -
 128         transitivity and antisymmetry.  In such cases, sort(x)
 129         may not give the results expected by the "intentions" of
 130         the comparisons expressed by "a < b".
 131
 132     In many sorting applications, appropriate precedes() functions
 133     have definitions equivalent to:
 134
 135                 define precedes(a,b) = (key(a) < key(b))
 136
 137     where key() maps possible values to a set totally ordered by <.
 138     Such a precedes() function has the properties (1) and (2),
 139     so the elements of the result returned by sort(x) will be in
 140     nondecreasing order of their key-values, elements with equal keys
 141     retaining the order they had in x.
 142
 143     For two-stage sorting where elements are first to be sorted by
 144     key1() and elements with equal key1-values then sorted by key2(),
 145     an appropriate precedes() function is given by:
 146
 147         define precedes(a,b) = (key(a) < key(b)) ||
 148                         (key(a) == key(b)) && (key2(a) < key2(b)).
 149
 150     When precedes(a.b) is called, the addresses of a and b rather
 151     than their values are passed to the function.  This permits
 152     a and b to be changed when they are being compared, as in:
 153
 154         define precedes(a,b) = ((a = round(a)) < (b = round(b)));
 155
 156     (A more efficient way of achieving the same result would be to
 157     use sort(round(x)).)
 158
 159     Examples of effects of various precedes functions for sorting
 160     lists of integers:
 161
 162         a > b                   Sorts into nonincreasing order.
 163
 164         abs(a) < abs(b)         Sorts into nondecreasing order of
 165                                 absolute values, numbers with the
 166                                 same absolute value retaining
 167                                 their order.
 168
 169         abs(a) <= abs(b)        Sorts into nondecreasing order of
 170                                 absolute values, possibly
 171                                 changing the order of numbers
 172                                 with the same absolute value.
 173
 174         abs(a) < abs(b) || abs(a) == abs(b) && a < b
 175                                 Sorts into nondecreasing order of
 176                                 absolute values, numbers with the
 177                                 same absolute value being in
 178                                 nondecreasing order.
 179
 180         iseven(a)               Even numbers in possibly changed order
 181                                 before odd numbers in unchanged order.
 182
 183         iseven(a) && isoddd(b)  Even numbers in unchanged order before
 184                                 odd numbers in unchanged order.
 185
 186         iseven(a) ? iseven(b) ? a < b : 1 : 0
 187                                 Even numbers in nondecreasing order
 188                                 before odd numbers in unchanged order.
 189
 190         a < b && a < 10         Numbers less than 10 in nondecreasing
 191                                 order before numbers not less than 10
 192                                 in unchanged order.
 193
 194         !ismult(a,b)            Divisors d of any integer i for which
 195                                 i is not also a divisor of d will
 196                                 precede occurrences of i; the order of
 197                                 integers which divide each other will
 198                                 remain the same; the order of pairs of
 199                                 integers neither of which divides the
 200                                 other may be changed.  Thus occurrences
 201                                 of 1 and -1 will precede all other
 202                                 integers; 2 and -2 will precede all
 203                                 even integers; the order of occurrences
 204                                 of 2 and 3 may change; occurrences of 0
 205                                 will follow all other integers.
 206
 207         1                       The order of the elements is reversed
 208
 209 EXAMPLES
 210     ; A = list(1, 7, 2, 4, 2)
 211     ; print sort(A)
 212
 213     list (5 elements, 5 nonzero):
 214           [[0]] = 1
 215           [[1]] = 2
 216           [[2]] = 2
 217           [[3]] = 4
 218           [[4]] = 7
 219
 220     ; B = list("pear", 2, null(), -3, "orange", null(), "apple", 0)
 221     ; print sort(B)
 222
 223     list (8 elements, 7 nonzero):
 224           [[0]] = NULL
 225           [[1]] = NULL
 226           [[2]] = -3
 227           [[3]] = 0
 228           [[4]] = 2
 229           [[5]] = "apple"
 230           [[6]] = "orange"
 231           [[7]] = "pear"
 232
 233     ; define precedes(a,b) = (iseven(a) && isodd(b))
 234     ; print sort(A)
 235
 236     list (5 elements, 5 nonzero):
 237           [[0]] = 2
 238           [[1]] = 4
 239           [[2]] = 2
 240           [[3]] = 1
 241           [[4]] = 7
 242
 243 LIMITS
 244     none
 245
 246 LINK LIBRARY
 247     none
 248
 249 SEE ALSO
 250     join, reverse
 251
 252 ## Copyright (C) 1999  Landon Curt Noll
 253 ##
 254 ## Calc is open software; you can redistribute it and/or modify it under
 255 ## the terms of the version 2.1 of the GNU Lesser General Public License
 256 ## as published by the Free Software Foundation.
 257 ##
 258 ## Calc is distributed in the hope that it will be useful, but WITHOUT
 259 ## ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 260 ## or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General
 261 ## Public License for more details.
 262 ##
 263 ## A copy of version 2.1 of the GNU Lesser General Public License is
 264 ## distributed with calc under the filename COPYING-LGPL.  You should have
 265 ## received a copy with calc; if not, write to Free Software Foundation, Inc.
 266 ## 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 267 ##
 268 ## @(#) $Revision: 30.1 $
 269 ## @(#) $Id: sort,v 30.1 2007/03/16 11:10:42 chongo Exp $
 270 ## @(#) $Source: /usr/local/src/cmd/calc/help/RCS/sort,v $
 271 ##
 272 ## Under source code control:   1995/07/09 19:41:26
 273 ## File existed as early as:    1995
 274 ##
 275 ## chongo <was here> /\oo/\     http://www.isthe.com/chongo/
 276 ## Share and enjoy!  :-)        http://www.isthe.com/chongo/tech/comp/calc/