Sort array with goal to minimize sequence repeat

Question

Ok so I have an array of websocket client connections. Imagine that this array contains connections to several different machines. Imagine that each different letter (1,2,3, etc) represents a different host. It might look like this:

const conns = [1,1,1,3,3,1,3,2,2,2,2,3,2,1,1,2,2];

what I would like to do, is sort the array like so:

const conns = [1,2,3,1,2,3,1,2,3, ... etc];

the rationale is if a client does not respond, I don't want to retry to the same host, I would like to try sending a message to a client on a different host, and only come back to the original host later. This is basically like a round-robin type thing.

I assume the best way to sort the array like this is:

1. find all the different hosts (unique letters) in the array
2. Iterate over this unique list, and splice off items from the original array as I go.

Here is the JS code I have for the above algorithm:

const list = [1,2,3,4,5,1,1,1,1,1,2,3,4,5,1,2,11,3,3,3,3,3,4,4,4,1,1,1];

const _ = require('lodash');

function findAndRemoveFirstMatch(m, list){
    for(var i = 0; i < list.length; i++){
        if(m === list[i]){
            return list.splice(i,1)[0];
        }
    }
}

function getSorted(list){

    const ret = [];

    const set = _.uniqBy(list, function(x){
        return x;
    });

    while(list.length > 0){

        var i = 0;
        while(i < set.length && list.length > 0){
            var item;
            if(item  = findAndRemoveFirstMatch(set[i],list)){
                ret.push(item);
            }
            i++;
        }

    }

    return ret;

}

console.log(getSorted(list));

//given the above input, we get:

[ 1, 2, 3, 4, 5, 11, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 3, 4, 1, 3, 4, 1, 3, 1, 3, 1, 1, 1 ]

I am not proud of this code, and am wondering if there is a better way to do it. The above works for this input, but looking for a good way to clean it up and make it more generic.

Is there a better/faster way to do this?

Answer 1

You can do it differently:

• sort input - it will help later

• find maximum count of equal elements (10 in your example, for element=1), cnt

• create cnt buckets to distribute elements over them

• put elements in sorted order one by one into next bucket with round-robin principle

• merge buckets

This way you get longer series in the end, 1 less than at the beginning.

[1, 2, 4, 1, 2, 4, 1, 2, 4, 1, 3, 4, 1, 3, 4, 1, 3, 5, 1, 3, 5, 1, 3, 11, 1, 3, 1, 3]

Bad case is when one element appears more than n/2 times, but that's unavoidable.

var list = [1,2,3,4,5,1,1,1,1,1,2,3,4,5,1,2,11,3,3,3,3,3,4,4,4,1,1,1];
var a = list.sort(function(a, b) { return a - b; });
var cnt = a.reduce(function(res, cur) {
  if (cur == res[0]) 
    return [cur, res[1]+1, Math.max(res[1]+1, res[2])]
  else
    return [cur, 1, Math.max(1, res[2])];
}, [null, 0, 0])[2];

var buckets = [];
for (var i = 0; i < cnt; i++)
  buckets[i] = [];

var j = 0;
for (var i = 0; i < a.length; i++) {
  buckets[j].push(a[i]);
  j = (j+1)%cnt;
}

var res = buckets.reduce(function(r, cur) {
  return r.concat(cur);
});

If you insist on full list of key from beginning, it's also possible:

var list = [1,2,3,4,5,1,1,1,1,1,2,3,4,5,1,2,11,3,3,3,3,3,4,4,4,1,1,1];
var a = list.sort(function(a, b) { return a - b; });
var cnt = a.reduce(function(res, cur) {
    if (cur == res[0]) 
        return [cur, res[1]+1, Math.max(res[1]+1, res[2])]
    else
        return [cur, 1, Math.max(1, res[2])];
}, [null, 0, 0])[2];

var buckets = [];
for (var i = 0; i < cnt; i++)
    buckets[i] = [];

var j = 0;
var cur = null;
for (var i = 0; i < a.length; i++) {
    if (cur != a[i]) 
        j = 0;
    buckets[j].push(a[i]);
    j = j+1;
}

var res = buckets.reduce(function(r, cur) {
    return r.concat(cur);
});