Abstract
We provide a new sorting algorithm which is optimal with respect to several known, and new, measures of presortedness. A new such measure, called Osc(X), measures the oscillation within the input data. The measure has an interesting application in the sweep-line technique in computational geometry. Our algorithm is based on a new approach which yields space efficiency and it uses simple data structures. For example, after a linear time preprocessing step, the only data structures used are a static tree and a heap.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
C.R Cook and D.J. Kim. Best sorting algorithms for nearly sorted lists. Communications of the ACM, 23(11):620–624, 1980.
H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin/Heidelberg, F.R. Germany, 1987.
V. Estivill-Castro and D. Wood. A new measure of presortedness. Research Report CS-87-58, University of Waterloo, Department of Computer Science, Waterloo, Canada, 1987.
L.J. Guibas, E.M. McCreight, M.F. Plass, and J.R. Roberts. A new representation of linear lists. In Proc. 9th Annual ACM Symposium on Theory of Computing, pages 49–60, 1977.
H Mannila. Implementation of a sorting algorithm suitable for presorted files. Technical Report, Department of Computer Science, University of Helsinki, Finland, 1984.
H. Mannila. Measures of presortedness and optimal sorting algorithms. IEEE Transactions on Computers, C-34(4):318–325, 1985.
K. Mehlhorn. Sorting presorted files. In Proc. 4th GI Conference on Theoretical Computer Science, pages 199–212, Springer-Verlag, 1979.
K. Mehlhorn. Data Structures and Algorithms, Vol 1: Sorting and Searching. Springer-Verlag, Berlin/Heidelberg, F.R. Germany, 1984.
K. Mehlhorn. Data Structures and Algorithms, Vol. 3: Multidimensional Searching and Computational Geometry. Springer-Verlag, Berlin/Heidelberg, F.R. Germany, 1984.
J. O'Rourke. Art Gallery Theorems and Algorithms. Oxford University Press, New York/Oxford, 1987.
F.P. Preparata and M.I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, N.Y., 1985.
S.S. Skiena. Encroaching lists as a measure of presortedness. BIT, 28:775–784, 1988.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Levcopoulos, C., Petersson, O. (1989). Heapsort—Adapted for presorted files. In: Dehne, F., Sack, J.R., Santoro, N. (eds) Algorithms and Data Structures. WADS 1989. Lecture Notes in Computer Science, vol 382. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-51542-9_41
Download citation
DOI: https://doi.org/10.1007/3-540-51542-9_41
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51542-5
Online ISBN: 978-3-540-48237-6
eBook Packages: Springer Book Archive