Zusammenfassung
Die Arbeit betrachtet Sortierverfahren für Systeme mit virtuellem Speicher. Es wird ein Algorithmus angegeben, für den die Fehlseitenrate immer unabhängig von der Zahln der Eintragungen der zu sortierenden Tabelle ist und allein von der Seitenzahl der Tabelle bestimmt ist. Das Fehlseitenverhalten stimmt in der Ordnungp logp mit dem Erwartungswert beim klassischen Quicksort überein, die Fehlseitenrate ist jedoch etwa um den Faktor 2 günstiger, und das vonn abhängende Verhalten bei teilweise sortierten Folgen wird vermieden.
Abstract
In this paper the behavior of sorting methods in a paging environment is studied. We give an algorithm which has a page fault rate always independant of the numbern of records in the file to be sorted and depending only on the number of pages required for the file. The expected number of page exceptions has with 0(p logp) the same order of magnitude as with the classic quicksort procedure but is by the factor 2 lower and we avoid the dependance onn in cases, when the sequence is in partial order.
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Literatur
Brown, B. S., Gustavson, F. G., Mankin, E. S.: Sorting in a Paging Environment. Com. ACM13, 183 (1970).
Knuth, D. E.: The Art of Computer Programming, Vol. 3. Reading, Mass.: 1972.
Hoare, C. A. R.: Quicksort. Comp. Journal5, 10 (1962/63).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Waldschmidt, H. Sortieren bei virtuellem Speicher. Computing 19, 1–14 (1977). https://doi.org/10.1007/BF02260737
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF02260737