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

Henglein, F 2009, 'What is a Sorting Function?', Journal of Logic and Algebraic Programming, vol. 78, no. 7, pp. 552-572. https://doi.org/10.1016/j.jlap.2008.12.003

APA

Henglein, F. (2009). What is a Sorting Function? Journal of Logic and Algebraic Programming, 78(7), 552-572. https://doi.org/10.1016/j.jlap.2008.12.003

Vancouver

Henglein F. What is a Sorting Function? Journal of Logic and Algebraic Programming. 2009;78(7):552-572. https://doi.org/10.1016/j.jlap.2008.12.003

Author

Henglein, Fritz. / What is a Sorting Function?. In: Journal of Logic and Algebraic Programming. 2009 ; Vol. 78, No. 7. pp. 552-572.

Bibtex

@article{8c8d7cb0e15711ddb5fc000ea68e967b,
title = "What is a Sorting Function?",
abstract = "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.",
author = "Fritz Henglein",
note = "Paper id:: doi:10.1016/j.jlap.2008.12.003",
year = "2009",
doi = "10.1016/j.jlap.2008.12.003",
language = "English",
volume = "78",
pages = "552--572",
journal = "Journal of Logic and Algebraic Programming",
issn = "2352-2208",
publisher = "Elsevier",
number = "7",

}

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