Sort a Javascript array based on every other element

Question

Assume that I have an array like so:

var a = [94, "Neptunium", 2, "Helium", null, "Hypotheticalium", 64, "Promethium"];

Even-numbered array indices are linked with the following odd index. In other words, 94 goes with "Neputunium" and 2 goes with "Helium" etc. How can I sort the array based on the even-numbered indices but keep the following odd-indexed value after it? So that I end up with an array like so:

a = [null, "Hypotheticalium", 2, "Helium", 64, "Promethium", 94, "Neptunium"];

NOTE: And yes, I do know that know that using an object or ES6 Map (or even, in this case, a sparse array with the numbers as indices, if null is left out) would be much more appropriate, but I'm just exploring this to experiment with the language. Thanks for any help.

You could in the first place do this: var a = [ ['a',1 ] ['b',2] ] — Manu Masson
– Manu Masson, Commented Sep 30, 2015 at 7:37

T.J. Crowder · Accepted Answer · 2015-09-30 07:53:41Z

5

Since the order of the calls to sort is not necessarily the same one JavaScript engine to the next (or even between revs of the same engine), you can't use sort directly on that array to do what you've described.

You can use map, filter, sort, then reduce however:

var a = [94, "Neptunium", 2, "Helium", null, "Hypotheticalium", 64, "Promethium"];
a = a
  .map(function(entry, index, array) {
    return (index % 2 === 1) ? null : {
      value: array[index + 1],
      index: entry
    };
  })
  .filter(function(entry) {
    return entry != null;
  })
  .sort(function(left, right) {
    return left.index - right.index; // Works even when either or both
                                     // indexes are null, PROVIDED
                                     // no non-null index is negative,
                                     // because `null` will coerce to 0
  })
  .reduce(function(acc, entry) {
    acc.push(entry.index, entry.value);
    return acc;
  }, []);
document.body.innerHTML = JSON.stringify(a);

The map lets us produce an array with objects for the paired entries (and nulls).

The filter lets us remove the nulls.

The sort lets us sort.

The reduce lets us produce an array of the results (since we can't use map directly to map one entry to two).

If you may have negative values for your even-numbered entries, the sort callback has to handle things differently because it will sort null above those negative indexes (unless of course that's what you want).

It's a bit more concise in ES6: (live on Babel's REPL)

let a = [94, "Neptunium", 2, "Helium", null, "Hypotheticalium", 64, "Promethium"];
a = a
  .map((entry, index, array) => {
    return (index % 2 === 1) ? null : {
      value: array[index + 1],
      index: entry
    };
  })
  .filter(entry => entry != null)
  .sort((left, right) => left.index - right.index)
  .reduce((acc, entry) => {
    acc.push(entry.index, entry.value);
    return acc;
  }, []);
console.log(a);

edited Sep 30, 2015 at 7:53

answered Sep 30, 2015 at 7:39

T.J. Crowder

1.1m201 gold badges2k silver badges2k bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

user162097 Over a year ago

That looks clever, but running the code gives me an unsorted result, albeit in a different order: [2,"Helium",null,"Hypotheticalium",94,"Neptunium",64,"Promethium"]

T.J. Crowder Over a year ago

@user162097: It's sorted by the names, did you mean it to be sorted by the numbers? Edit: Ah, you did, you said "even-numbered" indexes. Easily fixed.

user162097 Over a year ago

Oh yes, sorry. I did mean it to be sorted by the numbers, but I can work that much out myself. Thanks. I do wonder if there might not be more efficient ways of doing this with old-school algorithms (especially with very large arrays) than relying on all those function calls (and, in the process, changing my structure, or lack of it, to something else, even if more sensible), but nice answer.

T.J. Crowder Over a year ago

@user162097: Not with the built-in sort, no, not without making pretty big assumptions about the (e.g., that no two even-numbered entries will have the same value), but you could of course implement your own sorting function. The reason you can't do it with the built-in sort is that it doesn't give you the indexes of the elements it's calling you with, so you can't keep the odd-numbered entries with the even-numbered ones.

Nina Scholz Over a year ago

why do you use map and filter? only for preventing reduce?

|

deceze · Accepted Answer · 2015-09-30 07:36:51Z

5

var grouped = [];
for (var i = 0; i < a.length; i += 2) {
    grouped.push([a[i], a[i+1]]);
}

grouped.sort(function (a, b) { return a[0] - b[0]; });

Ideally I'd suggest you use the grouped structure from here on, since it seems to make more sense to group grouped items together, instead of relying on implicit adjacent indices. But if you need to unpack it again:

var b = [];
for (var i = 0; i < grouped.length; i++) {
    b.push.apply(b, grouped[i]);
}

answered Sep 30, 2015 at 7:36

deceze♦

525k89 gold badges806 silver badges954 bronze badges

1 Comment

deceze Over a year ago

BTW, I might be sorting on the wrong value here (numbers, not words), but you get the idea...

Nina Scholz · Accepted Answer · 2015-09-30 08:33:35Z

1

You need some grouping and appropriate sorting and reorganization of the array.

var array = [94, "Neptunium", 2, "Helium", null, "Hypotheticalium", 64, "Promethium"],
    sorted = array.reduce(function (r, a, i) {
        i % 2 ? r[r.length - 1].push(a) : r.push([a]);
        return r;
    }, []).sort(function (a, b) {
        return a[0] - b[0];
    }).reduce(function (r, a) {
        return r.concat(a);
    });
document.write('<pre>' + JSON.stringify(sorted, 0, 4) + '</pre>');

edited Sep 30, 2015 at 8:33

answered Sep 30, 2015 at 7:42

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Comments

user162097 · Accepted Answer · 2015-10-02 10:48:05Z

0

I like the ideas behind the JS-specific answers I've been given, but here's my own solution that doesn't rely on the native sort function and is instead based on an implementation of gnome sort:

var a = [94, "Neptunium", 2, "Helium", null, "Hypotheticalium", 64, "Promethium"];
for (var i = 0, temp; i < a.length; i += 2) {
    if (a[i] > a[i + 2]) {
        temp = a[i];
        a[i] = a[i + 2];
        a[i + 2] = temp;
        temp = a[i + 1];
        a[i + 1] = a[i + 3];
        a[i + 3] = temp;
        i = i - 4;
    }
}
alert(JSON.stringify(a));

Of course, it's not the fastest possible sorting algorithm, but just a proof-of-concept to show that it can be done without altering my lack of structure and without lots of (potentially expensive) function calls (although I do agree that functional programming is more of a JS idiom). And I could have put the swapping code into its own function, with two calls, for the sake of DRY, like so:

var a = [94, "Neptunium", 2, "Helium", null, "Hypotheticalium", 64, "Promethium"];
function arraySwapper(array, index1, index2) {
    var temp = array[index1];
    array[index1] = array[index2], array[index2] = temp;
}
for (var i = 0, j; i < a.length; i += 2) {
    if (a[i] > a[i + 2]) {
        for (j = i; j < i + 2; j++) { arraySwapper(a, j, j + 2); }
        i -= 4;
    }
}
alert(JSON.stringify(a));

edited Oct 2, 2015 at 10:48

answered Sep 30, 2015 at 8:35

user162097

1,26811 silver badges22 bronze badges

2 Comments

deceze Over a year ago

In a nutshell: you can implement any sorting algorithm you wish, of which there are many, and at the point where you swap items, you simply swap i and i + 1 together.

user162097 Over a year ago

@deceze Exactly! Well, almost: you also skip over two indices at a time, since every other one isn't used for comparison.

Collectives™ on Stack Overflow

Sort a Javascript array based on every other element

4 Answers 4

6 Comments

1 Comment

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

6 Comments

1 Comment

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related