RANDOM_SORTED
Generate Sorted Random Vectors

RANDOM_SORTED is a C++ library which generates vectors of random values which are already sorted.

Since the computation of the spacing between the values requires some additional arithmetic, it is not immediately obvious when this procedure will be faster than simply generating a vector of random values and then sorting it.

Because the library can generate a sorted random vector of values between 0 and 1, it is possible to generate sorted data samples from any distribution for which the inverse Cumulative Density Function (CDF) is known. For instance, to generate sorted normal data, simply generate sorted uniform data, and then apply the inverse of the normal CDF, as in the example code listed below.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

RANDOM_SORTED is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version and a Python version.

Related Data and Programs:

ASA183, a C++ library which implements the Wichman-Hill random number generator (RNG).

NORMAL, a C++ library which computes a sequence of pseudorandom normally distributed values.

RANDLC, a C++ library which generates a sequence of pseudorandom numbers, used by the NAS Benchmark programs.

RANLIB, a C++ library which produces random samples from Probability Density Functions (PDF's), including Beta, Chi-square Exponential, F, Gamma, Multivariate normal, Noncentral chi-square, Noncentral F, Univariate normal, random permutations, Real uniform, Binomial, Negative Binomial, Multinomial, Poisson and Integer uniform, by Barry Brown and James Lovato.

RNGLIB, a C++ library which implements a random number generator (RNG) with splitting facilities, allowing multiple independent streams to be computed, by L'Ecuyer and Cote.

UNIFORM, a C++ library which computes a sequence of uniformly distributed pseudorandom values.

VAN_DER_CORPUT, a C++ library which computes elements of a 1D van der Corput Quasi Monte Carlo (QMC) sequence using a simple interface.

Reference:

1. Jon Bentley, James Saxe,
   Generating sorted lists of random numbers,
   ACM Transactions on Mathematical Software,
   Volume 6, Number 3, September 1980, pages 359-364.

Source Code:

• random_sorted.cpp, the source code.
• random_sorted.hpp, the include file.

Examples and Tests:

• random_sorted_test.cpp, a sample calling program.
• random_sorted_test.txt, the output file.

List of Routines:

• NORMAL_01_CDF_INV inverts the standard normal CDF.
• R8_UNIFORM_01 returns a unit pseudorandom R8.
• R8POLY_VALUE_HORNER evaluates a polynomial using Horner's method.
• R8VEC_NORMAL_01_SORTED returns a sorted normal 01 random vector.
• R8VEC_TRANSPOSE_PRINT prints an R8VEC "transposed".
• R8VEC_UNIFORM_01 returns a unit pseudorandom R8VEC.
• R8VEC_UNIFORM_01_SORTED1 returns a sorted real random vector in [0,1].
• R8VEC_UNIFORM_01_SORTED2 returns a sorted real random vector in [0,1].
• TIMESTAMP prints the current YMDHMS date as a time stamp.

You can go up one level to the C++ source codes.