- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Sorting real numbers on random access machines
Open Collections
UBC Theses and Dissertations
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 Metadata
Title |
Sorting real numbers on random access machines
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
1995
|
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.
|
Extent |
2226298 bytes
|
Genre | |
Type | |
File Format |
application/pdf
|
Language |
eng
|
Date Available |
2009-02-09
|
Provider |
Vancouver : University of British Columbia Library
|
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.
|
DOI |
10.14288/1.0051188
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
1995-11
|
Campus | |
Scholarly Level |
Graduate
|
Aggregated Source Repository |
DSpace
|
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.