## 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?

Show source

## Answers to Sort array with goal to minimize sequence repeat ( 1 )

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