Open Collections

Sorting real numbers on random access machines

University of British Columbia

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.

Thesis/Dissertation

application/pdf

2009-02-09

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.

http://hdl.handle.net/2429/4328

Computer Science

University of British Columbia

UBCV

DSpace