UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Sorting real numbers on random access machines Blumenthal, Daniel S.

Abstract

This work describes a family, Segment-Sort, of algorithms for rapid sequential sorting of real numbers. Two computational models are discussed which correspond to the two main types of Segment-Sort algorithm: deterministic and random. With the deterministic model, the Basic RAM, it is possible to sort input populations randomly chosen from a broad class of common probability distributions in "space" (number of memory words, each able to hold a real number) and average time both linear in the number of real numbers given as input. Included among these distributions are a variety of types containing singularities, unbounded oscillations and points of actual nonzero probability (atoms). With the second model, the Random RAM, one may sort n arbitrarily chosen distinct real numbers in 0(n) operations using only 0(n) memory words on average. Except for random integer selection on the Random RAM , both models are confined to simple binary arithmetic. The power of both models appears to stem largely from the combination of left and right shifting operations.

Item Media

Item Citations and Data

Rights

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.