What is a Sorting Function?
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
What is a Sorting Function? / Henglein, Fritz.
In: Journal of Logic and Algebraic Programming, Vol. 78, No. 7, 2009, p. 552-572.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - What is a Sorting Function?
AU - Henglein, Fritz
N1 - Paper id:: doi:10.1016/j.jlap.2008.12.003
PY - 2009
Y1 - 2009
N2 - What is a sorting function—not a sorting function for a given ordering relation, but a sorting function with nothing given?Formulating four basic properties of sorting algorithms as defining requirements, we arrive at intrinsic notions of sorting and stable sorting: A function is a sorting function if and only it is an intrinsically parametric permutation function. It is a stable sorting function if and only if it is an intrinsically stable permutation function.We show that ordering relations can be represented isomorphically as inequality tests, comparators and stable sorting functions, each with their own intrinsic characterizations, which in turn provide a basis for run-time monitoring of their expected I/O behaviors. The isomorphisms are parametrically polymorphically definable, which shows that it is sufficient to provide any one of the representations since the others are derivable without compromising data abstraction.Finally we point out that stable sorting functions as default representations of ordering relations have the advantage of permitting linear-time sorting algorithms; inequality tests forfeit this possibility.
AB - What is a sorting function—not a sorting function for a given ordering relation, but a sorting function with nothing given?Formulating four basic properties of sorting algorithms as defining requirements, we arrive at intrinsic notions of sorting and stable sorting: A function is a sorting function if and only it is an intrinsically parametric permutation function. It is a stable sorting function if and only if it is an intrinsically stable permutation function.We show that ordering relations can be represented isomorphically as inequality tests, comparators and stable sorting functions, each with their own intrinsic characterizations, which in turn provide a basis for run-time monitoring of their expected I/O behaviors. The isomorphisms are parametrically polymorphically definable, which shows that it is sufficient to provide any one of the representations since the others are derivable without compromising data abstraction.Finally we point out that stable sorting functions as default representations of ordering relations have the advantage of permitting linear-time sorting algorithms; inequality tests forfeit this possibility.
U2 - 10.1016/j.jlap.2008.12.003
DO - 10.1016/j.jlap.2008.12.003
M3 - Journal article
VL - 78
SP - 552
EP - 572
JO - Journal of Logic and Algebraic Programming
JF - Journal of Logic and Algebraic Programming
SN - 2352-2208
IS - 7
ER -
ID: 9700072