Efficient way of alternating sort of array of objects based on property

Question

suppose we have an array of objects with one property called cat. How can we sort this array alternating the values based on the value of cat property on an efficient and cleaver way? suppose category value is always 'a' or 'b'.

given:

[
    {cat: 'a'}, {cat: 'b'},
    {cat: 'b'}, {cat: 'a'},
    {cat: 'b'}, {cat: 'b'},
    {cat: 'b'}, {cat: 'b'},
    {cat: 'b'}, {cat: 'a'}
]

expected output:

[
  { cat: 'a' },
  { cat: 'b' },
  { cat: 'a' },
  { cat: 'b' },
  { cat: 'a' },
  { cat: 'b' },
  { cat: 'b' },
  { cat: 'b' },
  { cat: 'b' },
  { cat: 'b' }
]

I implemented the solution bellow, but it seens quite strange:

let myArr = [
  {cat: 'a'}, {cat: 'b'},
  {cat: 'b'}, {cat: 'a'},
  {cat: 'b'}, {cat: 'b'},
  {cat: 'b'}, {cat: 'b'},
  {cat: 'b'}, {cat: 'a'}
]

alternatedSort = (it, i, arr) => {
  function findAlternatedValueIndex(lookupIndex, it, arr){
    if(lookupIndex < arr.length && arr[lookupIndex].cat == it['cat']){
      lookupIndex ++
      return findAlternatedValueIndex(lookupIndex, it, arr)
    }
    else 
      return lookupIndex < arr.length ? lookupIndex : undefined
  }

  var lookupIndex = i + 1

  if (lookupIndex < arr.length && arr[lookupIndex].cat == it['cat']){
    let tgtIndex = findAlternatedValueIndex(lookupIndex, it, arr)
    if (tgtIndex) {
      const aux = arr[lookupIndex]
      arr[lookupIndex] = arr[tgtIndex]
      arr[tgtIndex] = aux
    }
  }
}

myArr.forEach(function(it, i, arr) {
  alternatedSort(it,i, arr)
});


console.log("sorted array: ", myArr) 

obs: what is the complexity of the algorithm above and what is the best complexity we could get?

Answer 1

This is how I might approach this problem. While it isn't the most efficient, it is mostly likely sufficient efficient, and it is a general approach that applies to any number of keys. Variations of this concept are found relatively routinely in SQL queries.

The steps are as so:

• For every item generate a tuple [key, rank(key), item]. Here the rank(key) means the ordinal number of the occurrence of the key in relationship to other keys of the same value. There must be no gaps in the rank: that is, there are 1..3 ranks for 'a' and 1..6 ranks for 'b', and 1 for 'c'.
• Sort the tuples by rank(key) and then key.
• Extract the original item values.

Here is the concept in generalized JavaScript. There are libraries that can further abstract this approach.

Initially, given some items in different groups:

var items = [
    { cat: 'a', name: 'first a' },
    { cat: 'b', name: 'first b' },
    { cat: 'b' },
    { cat: 'a' },
    { cat: 'b' },
    { cat: 'b' },
    { cat: 'c', name: 'Mr. C' },
    { cat: 'b' },
    { cat: 'b', name: 'last b' },
    { cat: 'a', name: 'last a' }
]

Take the items and build a sequence of tuples that contain the rank per occurrence of the key. This is an O(n) operation.

var ranks = {}; // key -> last rank (undefined = 0)
var t = [];

for (let i of items) {
  var rk = (ranks[i.cat] = (ranks[i.cat] || 0) + 1);
  t.push([i.cat, rk, i]); 
}

Now t is as follows. (The duplication of key is intentional here to explain the concept, as well as for a more generic sort, although the sort could very well access the original object and thus eliminate a tuple index. Likewise, the original objects could be mutated to contain the rank.)

[
  [ 'a', 1, { cat: 'a', name: 'first a' } ],
  [ 'b', 1, { cat: 'b', name: 'first b' } ],
  [ 'b', 2, { cat: 'b' } ],
  [ 'a', 2, { cat: 'a' } ],
  [ 'b', 3, { cat: 'b' } ],
  [ 'b', 4, { cat: 'b' } ],
  [ 'c', 1, { cat: 'c', name: 'Mr. C' }, ],
  [ 'b', 5, { cat: 'b' } ],
  [ 'b', 6, { cat: 'b', name: 'last b' } ],
  [ 'a', 3, { cat: 'a', name: 'last a' } ]
]

Next, sort by the rank and then the key. This generic sort operation is O(n lg n), making it the algorithm’s big-O.

t.sort((a, b) => (a[1] - b[1]) || a[0].localeCompare(b[0]));

After the sort, t is:

[
  [ 'a', 1, { cat: 'a', name: 'first a' } ],
  [ 'b', 1, { cat: 'b', name: 'first b' } ],
  [ 'c', 1, { cat: 'c', name: 'Mr. C' } ],
  [ 'a', 2, { cat: 'a' } ],
  [ 'b', 2, { cat: 'b' } ],
  [ 'a', 3, { cat: 'a', name: 'last a' } ],
  [ 'b', 3, { cat: 'b' } ],
  [ 'b', 4, { cat: 'b' } ],
  [ 'b', 5, { cat: 'b' } ],
  [ 'b', 6, { cat: 'b', name: 'last b' } ]
]

Finally, loop through the tuple and extract the 3rd element, which corresponds with the original object. This is O(n).

var interwovenItems = t.map(x => x[2]);

Which yields the final result:

[
  { cat: 'a', name: 'first a' },
  { cat: 'b', name: 'first b' },
  { cat: 'c', name: 'Mr. C' },
  { cat: 'a' },
  { cat: 'b' },
  { cat: 'a', name: 'last a' },
  { cat: 'b' },
  { cat: 'b' },
  { cat: 'b' },
  { cat: 'b', name: 'last b' }
]

Answer 2

Another approach would be to go more generic. What if we had categories A, B, C, and D and wanted to cycle through them in sequence? What if the key were in a different property than cat?

This solution writes a simple function atop two more generic helpers. The first one, group, is similar to the groupBy functions found in many libraries, except that instead of returning an object keyed off the supplied function, it returns just an array of the arrays they generate. It could easily be built atop one of them by calling Object.values on the result.

The second helper, seqMerge, takes a array of arrays and rearranges them by picking the first values off each array in sequence, then the second from each, etc, simply skipping each array when it's empty. It looks like this:

seqMerge ([
  [1, 11], 
  [2, 22, 32, 42, 52, 62], 
  [3, 13, 33]
])
//=> [1, 2, 3, 11, 22, 13, 32, 33, 42, 52, 62]

With those, our main function becomes trivial:

const group = (fn) => (xs) => 
  Object .values (
    xs .reduce ((a, x) => ({...a, [fn (x)]: [... (a [fn (x)] || []), x]}), {})
  )

const seqMerge = ([[x = undefined, ...xs], ...xss]) => 
  x == undefined 
    ? xss .length == 0 ? [] : seqMerge (xss)
    : [x, ... seqMerge ([...xss, xs])]


const alternatingSort = (keyGen) => (xs) => 
  seqMerge (group (keyGen) (xs))

const xs = [{cat: 'a', id: 1}, {cat: 'b', id: 2}, {cat: 'b', id: 3}, {cat: 'a', id: 4}, {cat: 'b', id: 5}, {cat: 'b', id: 6}, {cat: 'b', id: 7}, {cat: 'b', id: 8}, {cat: 'b', id: 9}, {cat: 'a', id: 10}]

console .log (alternatingSort (x => x .cat) (xs))

.as-console-wrapper {max-height: 100% !important; top: 0}

Note that this version allows for as many categories as we like, not only two. It allows us to decide on a different property to use for partitioning the values, or even allows us to create a synthetic key for that. But using it is still simple.

Extensions

There are several ways we might want to extend this. There might be a reason to sort the groups we're going to yield. That would just mean doing something like this:

const alternatingSort = (keyGen) => (xs) => 
  seqMerge (
    group (keyGen) (xs) 
      .sort (([a], [b], x = keyGen (a), y = keyGen (b)) => x < y ? -1 : x > y ? 1 : 0)
  )

Or we might note what Rich Snapp has called the Reduce ({...spread}) antipattern, and decide to fix group up in a less elegant but more efficient manner with

const group = (fn) => (xs) => 
  Object .values (xs .reduce (
    (a, x, _, __, k = fn (x)) => ((a [k] = a [k] || []), (a [k] .push (x)), a),
    {}
  ))

or a more imperative version of the same idea.

And, while we're discussing performance, we might want to look at seqMerge more closely. I find that code elegant and quite beautiful. But it will bottom out when the combined list lengths approach the recursion depth limit, and will likely perform abysmally long before that. If you're using this for lists a few dozen long, then it won't be an issue.

We could rewrite it atop a transpose function. But it can't be any old transpose. My default version, (xs) => xs [0] .map ((_, i) => xs .map (r => r[i])), for instance, won't work here. transpose by the way, flips a rectangular grid, over its main diagonal. For instance:

transpose ([
  [1, 2, 3,  4,  5],
  [2, 3, 5,  7, 11],
  [1, 4, 9, 16, 25]
]) //=> 
// [
//   [1, 2, 1], 
//   [2, 3, 4], 
//   [3, 5, 9], 
//   [4, 7, 16], 
//   [5, 11, 25]
// ]

but the behavior on a ragged grid is undefined. And for this problem, we want to include all the results even if the columns aren't the same length. We can write a version that does so like this:

const transpose = (xs) => Array .from (
  {length: Math .max (... xs .map (r => r .length))}, 
  (_, i) => xs .map (r => r [i]) .filter ((x => x != null))
)

And then our sequential merge function is trivial:

const seqMerge = (xs) => 
  transpose (xs) .flat ()

Answer 3

'use strict'

catObjectArray = [
    {cat: 'a'}, {cat: 'b'},
    {cat: 'b'}, {cat: 'a'},
    {cat: 'b'}, {cat: 'b'},
    {cat: 'b'}, {cat: 'b'},
    {cat: 'b'}, {cat: 'a'}
]

catObjectsByType = {
    'a': catObjectArray.filter(object =>  object.cat === 'a').length,
    'b': catObjectArray.filter(object =>  object.cat === 'b').length
}

let totalCatObjects = catObjectsByType.a + catObjectsByType.b

let sortedArrayOfCats = []

while (totalCatObjects !== 0){
    if(catObjectsByType.a > 0){
        if(totalCatObjects % 2 === 0){
            sortedArrayOfCats.push({cat: 'a'})
            catObjectsByType.a = catObjectsByType.a - 1
        } else {
            if(catObjectsByType.b > 0){
                sortedArrayOfCats.push({cat: 'b'})
                catObjectsByType.b = catObjectsByType.b - 1
            } else {
                sortedArrayOfCats.push({cat: 'a'})
                catObjectsByType.a = catObjectsByType.a - 1 
            }
        }
        totalCatObjects -= 1

    } else {
        sortedArrayOfCats.push({cat: 'b'})
        catObjectsByType.b = catObjectsByType.b - 1
        totalCatObjects -= 1
    }
}

console.log(sortedArrayOfCats)
/*
(10) [{…}, {…}, {…}, {…}, {…}, {…}, {…}, {…}, {…}, {…}]
0: {cat: "a"}
1: {cat: "b"}
2: {cat: "a"}
3: {cat: "b"}
4: {cat: "a"}
5: {cat: "b"}
6: {cat: "b"}
7: {cat: "b"}
8: {cat: "b"}
9: {cat: "b"}
*/

Answer 4

I'd simply split the array by cat and then merge the results alternating.

let cata = arr.filter(x=> x.cat === 'a');
let catb = arr.filter(x=> x.cat === 'b');

let newarr =[];
let i = 0;

while (cata[i] || catb[i]) {
  if (cata[i]) newarr.push(cata[i]);
  if (catb[i]) newarr.push(catb[i]);
  i++;
}

That's in O(n), because it's just 3 iterations of the array. And O(n) is the best you can get, as you have to look at each element in the array at least once.

Another approach doesn't need to split the array beforhand. It needs a total of 2 iterations through the array (once for each category) and fills the new array while traversing.

let newarr = [];
let a = 0, b = 0;
while (arr[a] || arr[b]) {
  while (arr[a]?.cat === 'b') a++;
  while (arr[b]?.cat === 'a') b++;
  
  if (arr[a])
    newarr.push(arr[a++])
  
  if (arr[b])
    newarr.push(arr[b++])
}

A completely different approach, doing it in place (but at the cost of an additional property) with the built-in Array.sort could be the following

Assign to each element if it's the 1st, 2nd, ... of its category. Then sort by that order property. If two elements have the same order, sort a before b

let a=0, b=0;
for (let e of arr) {
  e.order = e.cat === 'a' ? a++ : b++
}

arr.sort((x,y) => { 
  if (x.order === y.order) 
    return x.cat === 'a' ? -1 : +1;
  return x.order - y.order;
})

Of course this is at least O(n logn), depending on the sort algorithm used by the JS engine.