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