Generating Sorted Lists of Random Numbers.

Abstract

The empirical testing of a program often calls for generating a set of random numbers and then immediately sorting them. In this paper we consider the problem of accomplishing that process in a single step: generating a sorted list of random numbers (specifically, reals chosen uniformly from (0,1)). The method we describe generates the randoms in linear time, is perfectly random (if it can call a perfectly random generator for a single uniform), and can be described in just three lines of Algol or Pascal code. If the numbers are not required to be generated all at once (but are rather to be used one-at-a-time), then the method can be implemented as a subroutine to produce the next number and requires only constant storage. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1979
Accession Number
ADA066739

Entities

People

  • James B. Saxe
  • John Louis Bentley

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computer Programming
  • Computers
  • Data Science
  • Demographic Cohorts
  • Information Science
  • Military Research
  • Monotone Functions
  • Numbers
  • Order Statistics
  • Probability
  • Probability Distributions
  • Programming Languages
  • Random Number Generators
  • Random Variables
  • Real Numbers
  • Statistics

Fields of Study

  • Computer science

Readers

  • Approximation Theory.
  • Graph Algorithms and Convex Optimization.