Back to search

University of British Columbia

Sorting real numbers on random access machines

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
1995

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Blumenthal, Daniel S.

Rights

dc:rights
Statement dc: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.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/4328

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Blumenthal, Daniel S.. Sorting real numbers on random access machines. master's thesis, University of British Columbia, 1995. http://hdl.handle.net/2429/4328