Home > Blockchain >  Algorithm to maintain a sorted (numerically) list of numbers/doubles
Algorithm to maintain a sorted (numerically) list of numbers/doubles

Time:11-30

Say I am generating random numbers using Math.random(), maybe 1000 of them, and I want to have them in ascending order (at all times). Is there a data structure of some variety that can keep them sorted the whole time, without ever having to call a sort routine? The only thing I can think of is a heap? but there might be a better way.

Some code will help:

const numContainer = {};

for(let i = 0; i < 1000; i  ){
   const r = Math.random();  // I generate a new RV
   numContainer[r] = {r};   // I want to store it in order, but this isn't helping :-)
}

clearly the above is not really going to maintain any numerical order for the keys etc. I am looking to have them be sorted as I go.

CodePudding user response:

You can generate your numbers in sorted order in linear time. The paper describing how to do this is: Generating Sorted Lists of Random Numbers by Bentley & Saxe

https://pdfs.semanticscholar.org/2dbc/4e3f10b88832fcd5fb88d34b8fb0b0102000.pdf

/**
 * Generate an sorted list of random numbers sorted from 1 to 0, given the size
 * of the list being requested.
 * 
 * This is an implementation of an algorithm developed by Bentley and Sax, and
 * published in in ACM Transactions on Mathematical Software (v6, iss3, 1980) on
 * 'Generating Sorted Lists of Random Numbers'.
 */
public class SortedRandomDoubleGenerator {
    private long       valsFound;
    private double     curMax;
    private final long numVals;

    /**
     * Instantiate a generator of sorted random doubles.
     * 
     * @param numVals the size of the list of sorted random doubles to be
     *        generated
     */
    public SortedRandomDoubleGenerator(long numVals) {
        curMax = 1.0;
        valsFound = 0;
        this.numVals = numVals;
    }

    /**
     * @return the next random number, in descending order.
     */
    public double getNext() {
        curMax = curMax
                * Math.pow(Math.E, Math.log(RandomNumbers.nextDouble())
                        / (numVals - valsFound));
        valsFound  ;
        return curMax;
    }
}

CodePudding user response:

A heap is only partially ordered: nodes are only ordered with respect to their parents. Perhaps you were thinking of a binary search tree.

A typical implementation of a self-balanced binary search tree is the red-black tree, and it can be implemented using an array with some empty spaces (at most n-2 if you have n elements).

The whole operation will still run in the same amount of time, complexity-wise, as just populating an array and sorting it at the end, although I would bet the latter option is almost always faster.

CodePudding user response:

You did not specify any constraint on the data structure, so an elementary solution is an array, combined with insertion of the new elements.

Or a linked list.

Or a binary search tree.

But not a heap !

  • Related