=Paper=
{{Paper
|id=None
|storemode=property
|title=An Explicit Formula for Sorting and its Application to Sorting in Lattices
|pdfUrl=https://ceur-ws.org/Vol-1032/paper-12.pdf
|volume=Vol-1032
|dblpUrl=https://dblp.org/rec/conf/csp/Gerlach13
}}
==An Explicit Formula for Sorting and its Application to Sorting in Lattices==
https://ceur-ws.org/Vol-1032/paper-12.pdf
An Explicit Formula for Sorting and its Application to
Sorting in Lattices
Jens Gerlach
Fraunhofer FOKUS
jens.gerlach@fokus.fraunhofer.de
Abstract In a totally ordered set the notion of sorting a finite sequence is de-
fined through the existence of a suitable permutation of the sequence’s indices. A
drawback of this definition is that it only implicitly expresses how the elements
of a sequence are related to those of its sorted counterpart. To alleviate this situa-
tion we prove a simple formula that explicitly describes how the kth element of a
sorted sequence can be computed from the elements of the original sequence. As
this formula relies only on the minimum and maximum operations we use it to
define the notion of sorting for lattices. A major difference of sorting in lattices
is that it does not guarantee that sequence elements are only rearranged. To the
contrary, sorting in general lattices may introduce new values into a sequence or
completely remove values from it. We can show, however, that other fundamental
properties that are associated with sorting are preserved. Furthermore, we address
the problem that the direct application of our explicit formula for sorting leads to
an algorithm with exponential complexity. We present therefore for distributive
lattices a recursive formulation to compute the sort of a sequence.
n−1 This alterna-
tive formulation, which is inspired by the identity nk = n−1 k−1
+ k that underlies
Pascal’s triangle, allows for sorting in lattices with quadratic complexity and is in
fact a generalization of insertion sort for lattices.
1 Introduction
In this paper we present the results of two preprints [1,2] where we outline basic prin-
ciples of a theory of sorting in lattices.
Sorting a sequence in a total order (X, ≤) is typically defined through the existence
of a suitable permutation (cf. [3, p. 4]). There exists for each sequence x of length n in
a totally ordered set a permutation ϕ of [1, n] = {1, . . . , n} such that x ◦ ϕ is a increasing
sequence. If x is injective, then ϕ is uniquely determined, and vice versa. However,
regardless whether there is exactly one permutation, the rearrangement x↑ = x ◦ ϕ is
uniquely determined and we thus refer to it as the increasing sort of x.
Sorting defines a map x 7→ x↑ from X n to the subset of increasing sequences. This
map has several interesting properties. First of all, it is idempotent
x↑ ↑ = x↑ (1)
and thus a projection. Secondly, for each permutation ψ of [1, n] we have
(x ◦ ψ)↑ = x↑ (2)
134 J. Gerlach
The definition of sorting through the existence of a suitable permutation only pro-
vides an implicit relationship between the elements of x and x↑ . However, sometimes
we prefer explicit relationships.
If, for example, someone asked whether there is for the numbers a and b and the
exponent n a general relationship between the value (a + b)n and the powers an and bn ,
then the (obvious) answer is that this relationship is captured by the Binomial Theorem
n !
X n n−k k
(a + b)n = a b (3)
k=0
k
which also shows that other powers of a and b are involved.
When looking for an explicit relationship between
the elements
of x and the ele-
ments of its increasingly sorted counterpart x↑ = x1↑ , . . . , xn↑ , one can provide an easy
answer for the first and last elements of x↑ . In fact, we know that x1↑ is the least element
of {x1 , . . . , xn }
n
^
x1↑ = x1 ∧ . . . ∧ xn = xk , (4)
k=1
whereas xn↑ is the greatest element of x
n
_
xn↑ = x1 ∨ . . . ∨ xn = xk . (5)
k=1
In Section 2 we prove Identity (7) that explicitly states how the elements x1↑ , . . . , xn↑
are related to x1 , . . . , xn . This formula only uses the minimum and maximum operations
on finite sets. Based on this observation, we define in Section 3 the notion of sorting of
sequences in a lattice through simply replacing the minimum/maximum operations by
the infimum/supremum operations, respectively. We also show that sorting in lattices in
general not just reorders the elements of a sequence but really changes them. However,
we are able to prove that our definition satisfies various properties that are associated
with sorting.
The direct application of Identity (7) leads to an algorithm with exponential com-
plexity (cf. Section 4). In order to address this problem, we prove the recursive Iden-
tity (19) for the case of bounded distributive lattices. This identity is closely related to
the well-known fact that the binomial coefficient
!
n n!
=
k k! · (n − k)!
can be efficiently computed through the recursion
! ! !
n n−1 n−1
= +
k k−1 k
which underlies Pascal’s triangle.
Furthermore, we prove that a lattice, in which the recursive Identity (19) holds, is
necessarily distributive. The main advantage of our recursive identity is that it allows
for an algorithm for sorting in lattices with quadratic complexity. In fact, this algorithm
is a generalization of insertion sort for lattices (cf. Section 5).
An Explicit Formula for Sorting and its Application to Sorting in Lattices 135
2 A formula for sorting
Let (X, ≤) be a totally ordered set, then each nonempty finite subset A of X contains a
least and a greatest element [4, R. 6.5]. We also speak of the minimum and maximum
V W
of A and refer to these special elements as A and A, respectively. The following
inequalities hold for all a ∈ A
^ _
A≤a≤ A (6)
For A = {x, y} we use the notation x ∧ y and x ∨ y to denote the minimum and maximum
of x and y, respectively.
The main results of this paper depend on a particular family of finite sets.
n o
Definition 1. For k ∈ [1, n] we denote with N nk B A ⊂ [1, n] |A| = k the set of
n n
subsets of [1, n] that contain exactly k elements. The set N k consists of k elements.
Proposition 1. Let (x1 , . . . , xn ) be a sequence in a totally ordered
set, then the following
identity holds for the elements of the sequence x1↑ , . . . , xn↑
^ _
xk↑ = xi . (7)
I∈N(nk) i∈I
Before we prove Proposition 1 we introduce an abbreviation for the right hand side
of Identity (7). For a sequence x of length n we define for 1 ≤ k ≤ n
^ _
xkM B xi . (8)
I∈N(nk) i∈I
With this notation Proposition 1 reads
x↑ = xM . (9)
We remark that because (X, ≤) is a total order, we know that each element of xM is also
an element of x. When applying Identity (8) it is sometimes convenient to use a slightly
more explicit way to write the elements of xM .
^
xkM = xi1 ∨ . . . ∨ xik (10)
1≤i1 <...) is a bounded lattice.
Here ⊥ is the least element of X and the neutral element of join, that is,
x=⊥∨x= x∨⊥ ∀x ∈ X (14)
whereas > is the greatest element of X and the neutral element of meet, that is,
x=>∧x= x∧> ∀x ∈ X. (15)
We now introduce a notation that allows us to concisely refer to individual elements
of both (x1 , . . . , xn )M and (x1 , . . . , x n−1
)M . Here again, it is convenient to employ the no-
tation for the binomial coefficient nk in the context of sorting in lattices. For a sequence
x of length n we define for 0 ≤ m ≤ n
⊥ k=0
M m
, . . . ,
M
x k B k ∈ [1, m] (16)
(x 1 xm ) (k)
k =m+1
>
^ _
We know from Identity (8) that (x1 , . . . , xm )M (k) = xi holds for 1 ≤ k ≤ m.
I∈N(mk) i∈I
We therefore have
^ _
xM mk = xi . (17)
I∈N(mk) i∈I
In particular, the following identity holds for 1 ≤ k ≤ n
xM nk = xkM . (18)
The main result of this section is Proposition 2, which states in Identity (19), how
the kth element of (x1 , . . . , xn )M can be computed from (x1 , . . . , xn−1 )M and xn by simply
applying one join and one meet. The proof of Proposition 2 relies on the fact that the
lattice under consideration is both bounded and distributive.
140 J. Gerlach
Proposition 2. If (X, ∧, ∨, ⊥, >) is a bounded distributive lattice and if x is a sequence
of length n, then for 1 ≤ k ≤ n holds
n−1
xM nk = xM n−1 M
k ∧ x k−1 ∨ xn (19)
Proof. For k = 1, we have
^ n
xM n1 = xi by Identity (17)
i=1
n−1
^
= xi ∧ xn by associativity
i=1
= xM n−1 1 ∧ xn by Identity (17)
n−1
= x M 1 ∧ ⊥ ∨ xn by Identity (14)
n−1
= xM n−1 1 ∧ x M
0 ∨ x n by Identity (16).
We deal similarly with the case k = n (cf. [2, p. 5]). In the general case of 1 < k < n,
we first remark that if A is a subset of [1, n], which consists of k elements, then there
are two cases possible:
1. If n does not belong to A, then A is a subset of N n−1
k .
2. If n is an element of A, then the set B B A \ {n} belongs to N n−1
k−1 .
n
In other words, N k can be represented as the following (disjoint) union
n n−1o
N nk = N n−1k ∪ B ∪ {n} B ∈ N k−1 . (20)
We obtain therefore
^ _
xM nk = xi by Identity (17)
I∈N(nk) i∈I
^ _ ^ _
= xi ∧ xi by Identity (20)
n−1 i∈I
I∈N( k ) I∈N n−1
(
k−1 ) i∈I∪{n}
^ _
= xM n−1 k ∧ xi by Identity (17)
I∈N(n−1
k−1)
i∈I∪{n}
^ _
= xM n−1
k ∧ x ∨ x
i n by associativity
I∈N(n−1 i∈I
k−1)
^ _
= xM n−1
k ∧ xi ∨ xn by distributivity
i∈I
I∈N(n−1
k−1)
= xM n−1
k ∧ xM n−1k−1 ∨ x n by Identity (17)
which completes the proof. t
u
An Explicit Formula for Sorting and its Application to Sorting in Lattices 141
The following Proposition 3 states that the converse of Proposition 2 also holds.
Proposition 3. Let (X, ∧, ∨, ⊥, >) be a bounded lattice which is not distributive. Then
there exists a sequence x = (x1 , x2 , x3 ) in X such that Identity (19) is not satisfied.
Proof. According to a standard result on distributive lattices [5, Theorem 4.7], a lattice
is not distributive, if and only if it contains a sublattice which is isomorphic to either N5
or M3 (cf. Figure 2).
e e
d
c b c d
b
a
N5 a
M3
Figure 2. The non-distributive lattices N5 and M3
From Identity (10) follows for the elements of xM = x1M , x2M , x3M
x1M = x1 ∧ x2 ∧ x3 (21a)
x2M = (x1 ∨ x2 ) ∧ (x1 ∨ x3 ) ∧ (x2 ∨ x3 ) (21b)
x3M = x1 ∨ x2 ∨ x3 . (21c)
If X contains the sublattice N5 , then we consider the sequence x = (c, d, b) and its
subsequence (c, d). From Identity (21) then follows
(c, d, b)M = (a, d, e) and (c, d)M = (a, e).
Thus, we have
xM 32 = d xM 22 = e xM 21 = a.
However, applying Identity (19) we obtain
xM 32 = xM 22 ∧ xM 21 ∨ x3
= e ∧ (a ∨ b) = e ∧ b = b
instead of d.
If X contains the sublattice M3 , then we consider the sequence x = (b, c, d) and its
subsequence (b, c). From Identity (21) then follows
(b, c, d)M = (a, e, e) and (b, c)M = (a, e).
142 J. Gerlach
We therefore have
xM 32 = e xM 22 = e xM 21 = a.
Again, applying Identity (19) we obtain
xM 32 = xM 22 ∧ xM 21 ∨ x3
= e ∧ (a ∨ d) = e ∧ d = d
instead of e. t
u
Using Identity (19), we can prove the following Lemma 6, which generalizes a
known fact known from sorting in a total order: If one knows that xn is greater or equal
that the preceding elements x1 , . . . , xn−1 then sorting the sequence (x1 , . . . , xn ) can be
accomplished by sorting (x1 , . . . , xn−1 ) and simply appending xn .
Lemma 6. Let (X, ∧, ∨, ⊥, >) be a bounded distributive lattice and x be a sequence of
length n. If the condition xi ≤ xn holds for 1 ≤ i ≤ n − 1, then the identities
xM ni = xM n−1i
x n = xn
M n
hold.
Proof. The first equation follows directly from the fact that xnM is the supremum of the
values x1 , . . . , xn . Regarding the second equation, we know from Lemma 2 that if for
1 ≤ i ≤ n − 1 the inequality xi ≤ xn holds, then
xM n−1
i ≤ xn .
0 = ⊥ holds by Identity (16). From
This inequality is also valid for i = 0 because xM n−1
general properties of meet and join then follows that
xM n−1
i ∨ xn = xn
n−1
xM i ∧ xn = xM n−1 i
holds for 0 ≤ i ≤ n − 1. We can therefore simplify Identity (19) as follows
n−1
xM ni = xM n−1
i ∧ xM i−1 ∨ xn
= xM n−1
i ∧ xn
=x i .
M n−1
t
u
An Explicit Formula for Sorting and its Application to Sorting in Lattices 143
✓ ◆
1
x1 xM
? 1 >
↙ ↙
↙
↙
✓ ◆ ✓ ◆
2
x2 xM
2 xM
? 1 2 >
↙ ↙ ↙
↙
↙
↙
✓ ◆ ✓ ◆ ✓ ◆
M 3 M 3 M 3
x3 x x x
? 1 2 3 >
Figure 3. Graphical representation of Identity (19)
5 Insertion sort in lattices
Figure 3 graphically represents Identity (19) in a form that emphasizes its close rela-
tionship to Pascal’s triangle. Whenever an arrow & and and arrow . meet, the values
are combined by a meet. In the case of an arrow &, however, first the value at the origin
of the arrow is combined with the sequence value xn through a join.
Formula (22) outlines an algorithm that is based on Identity (19). The algorithm
starts from x1 = (x1 )M and successively computes
(x1 , . . . , xi−1 )M , xi 7→ (x1 , . . . , xi−1 , xi )M . (22)
From Identity (19) follows that in step i exactly i joins and i meets must be performed.
Thus, altogether there are
Xn
2 ∗ i = n(n + 1) − 2
i=2
applications of join and meet. In other words, such an implementation has quadratic
complexity. This algorithm can be considered as insertion sort [3, § 5.2.1] for lattices
because one element at a time is added to an already “sorted” sequence. Table 3 shows
some performance measurements for this algorithm in the bounded and distributive
lattice (N, gcd, lcm, 1, 0).
sequence length 100 1000 10000 100000
time in s 0 0 3.4 420
Table 3. Wall-clock time for computing (1, . . . , n)M according to Identity (19)
These results show that sorting in lattices can now be applied to much larger se-
quences than those shown in Table 2 before the limitations of an algorithm with quadratic
complexity become noticeable.
144 J. Gerlach
6 Conclusions
Proposition 1 states through Identity (7) a simple explicit relationship between the ele-
ments of a finite sequence in a totally ordered sets to its sorted counterpart.
A sorting algorithm that directly uses Identity (7) would have exponential complex-
ity. Thus, Identity (7) appears not relevant for implementing computationally efficient
algorithms. The reader should bear in mind, however, that this is also true for the Bi-
nomial Theorem. In fact, directly computing (x + y)n is normally more efficient than
computing the expansion
n(n − 1) n−2 2
xn + nxn−1 y + x y + . . . + yn
2
A more interesting aspect of Identity (7) is therefore that it allows to generalize the
notion of sorting finite sequences to lattices. Compared to sorting in a totally ordered
set, sorting in lattices is a more invasive procedure because it may change sequence
elements. While this may be considered as a major drawback one should bear in mind
that generalizations often lead to surprising properties. The real criterion for accepting
a generalization is whether it provides new insights or has useful applications. With
respect to sorting in lattices, the latter question has not been addressed in this paper and
remains a topic of future research.
We are able to show that our definition of sorting in lattices maintains many proper-
ties that are associated with sorting. Another important results of this paper are Propo-
sition 2, which proves Identity (19) for bounded distributive lattices, and Proposition 3,
which shows that the distributivity is necessary for Identity (19) to hold. The remarkable
points of Identity (19) are that it
– exhibits a strong analogy between sorting and Pascal’s triangle,
– allows to sort in lattices with quadratic complexity, and that it
– is in fact a generalization of insertion sort for lattices.
I would like to thank the reviewers for their comments. I am also very grateful for
the many corrections and valuable suggestions of my colleagues Jochen Burghardt and
Hans Werner Pohl: Jochen Burghardt’s suggestion to investigate whether the distributiv-
ity in Proposition 2 is really necessary led to Proposition 3. Hans Werner Pohl pointed
out the analogy of the algorithm in Equation 22 to insertion sort.
References
1. J. Gerlach. Sorting in Lattices. ArXiv e-prints, March 2013.
http://arxiv.org/abs/1303.5560.
2. J. Gerlach. Recursive Sorting in Lattices. ArXiv e-prints, May 2013
http://arxiv.org/abs/1306.0019.
3. Donald E. Knuth. The Art of Computer Programming, Volume III: Sorting and Searching.
Addison-Wesley, 1973.
4. Bourbaki, N., Elements of Mathematics, Theory of Sets, Addison-Wesley, Reading, MA,
1968.
5. S. Roman. Lattices and Ordered Sets. Springer-Verlag New York, 2008.