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
|
\DOC sort
\TYPE {sort : ('a -> 'a -> bool) -> 'a list -> 'a list}
\SYNOPSIS
Sorts a list using a given transitive `ordering' relation.
\DESCRIBE
The call
{
sort op list
}
\noindent where {op} is a transitive relation on the elements of {list}, will
topologically sort the list, i.e. will permute it such that if {x op y} but not
{y op x} then {x} will occur to the left of {y} in the sorted list. In
particular if {op} is a total order, the list will be sorted in the usual sense
of the word.
\FAILURE
Never fails.
\EXAMPLE
A simple example is:
{
# sort (<) [3; 1; 4; 1; 5; 9; 2; 6; 5; 3; 5; 8; 9; 7; 9];;
val it : int list = [1; 1; 2; 3; 3; 4; 5; 5; 5; 6; 7; 8; 9; 9; 9]
}
\noindent The following example is a little more complicated, and shows how a
topological sorting under the relation `is free in' can be achieved. This is
actually sometimes useful to consider subterms of a term in an appropriate
order:
{
# sort free_in [`(x + 1) + 2`; `x + 2`; `x:num`; `x + 1`; `1`];;
val it : term list = [`1`; `x`; `x + 1`; `x + 2`; `(x + 1) + 2`]
}
\COMMENTS
This function uses the Quicksort algorithm internally, which has good
typical-case performance and will sort topologically. However, its worst-case
performance is quadratic. By contrast {mergesort} gives a good worst-case
performance but requires a total order. Note that any comparison-based
topological sorting function must have quadratic behaviour in the worst case.
For an $n$-element list, there are $n (n - 1) / 2$ pairs. For any topological
sorting algorithm, we can make sure the first $n (n - 1) / 2 - 1$ pairs
compared are unrelated in either direction, while still leaving the option of
choosing for the last pair $(a,b)$ either $a < b$ or $b < a$, eventually giving
a partial order. So at least $n (n - 1) / 2$ comparisons are needed to
distinguish these two partial orders correctly.
\SEEALSO
mergesort.
\ENDDOC
|
