Algorithm to maintain a sorted (numerically) list of numbers (Doubles)

Question

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 an algorithm 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 BST? 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.

Update 1: I realize the use-case might be good to know (or interesting). The use-case is a discrete-event-simulation, the smaller the random uniform variable the sooner the event, so I need to read the events in numerical order so it would be nice if they were sorted, naturally, instead of requiring a sort or what not.

Update 2: I realized binary search (with an array), won't really be much good since I will have to insert the new item and that insert will end up being O(n), so back to square one. So my guess is just some sort algorithm that works with an already sorted array, will be fastest?

Answer 1

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;
    }
}

Answer 2

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.

Answer 3

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 !

Answer 4

As the others who commented have said, there is not really an "automatic" way of doing this in linear time, but i've been using something similar to the following implementation to maintain an ordered realtime orderbook and it has been plenty fast (and contains way more than 1000 values) so far. I just made it a "special" type of array-object, the actual implementation can of course be changed any way you like, i just hijacked the Array.push() method here for a binaryInsert and wanted the other array methods to be available as well, not sure if that's what you're looking for, but maybe it helps somehow:

var data = Array.from({length: 1000}, () => Math.random() * 20);

var sortedArray = Object.create(Array.prototype, {
    compare: {
        value: (a, b) => a - b
    },
    push: {
         value: function(...items) {
            items.forEach((item) => {
                let low = 0;
                let high = this.length;
                
                while (low < high) {
                    const mid = (low + high) >> 1;
                    this.compare(this[mid], item) > 0
                        ? (high = mid)
                        : (low = mid + 1);
                }
            
                this.splice(low, 0, item);
            });

            return this.length;
        }
    }
});

// you can push your random values individually
//const s = performance.now();
//data.forEach((rand) => sortedArray.push(rand));
//const e = performance.now();
//console.log(`individually inserted ${data.length} items sorted in ${e-s}ms`);

// or in bulk, like normal .push()
const s = performance.now();
sortedArray.push(...data);
const e = performance.now();
console.log(`batch inserted ${data.length} items sorted in ${e-s}ms`);

// you can do anything you can with a regular Array, like
console.log('filtered', sortedArray.filter((value) => value >= 10 && value <= 11));

console.log(sortedArray);

Answer 5

The short answer is that, no, you can't end up with a continuously sorted dense array in constant time.

The closest thing that comes to mind is kind of a cross between a Radix sort and a hash table.

Start with an array of 10000 null entries, say, and slot each value into slot # floor(10000*value), where value is a random number from [0-1).

Inserting is O(1), just like a hash table. And everything is sorted... But it's sparse.

You have to expect hash collisions, of course, so each slot would either be a linked list of values or you could "bubble" consecutive values forward in the array to keep it sorted.

That would give you roughly O(n) for inserts, though O(m) for iterating through the list, where m is the total hash table size.

Not sure if this is useful for your goal here, but it seemed like a different approach that someone might find useful.

Answer 6

@Alexander Mills. If I well understand your statement "So my guess is just some sort algorithm that works with an already sorted array, will be fastest?", I think you're close to the solution, which is an array or table of queues sorted in priority order. One can't avoid prioritizing the discrete events. If the discrete events are not prioritized, it's a typical "Last In, First Serve" situation! It looks like you're trying to simulate a multithreaded system. Am I right? To answer your question "Is there an algorithm of some variety that can keep them sorted the whole time, without ever having to call a sort routine?": if you're looking for a background sorting, the only way is a Thread!