36

Suppose I have this array:

var array = [
  { name: "border-color", value: "#CCCCCC" },
  { name: "color", value: "#FFFFFF" },
  { name: "background-color", value: "rgb(0, 0, 0)" },
  { name: "background-color", value: "rgba(0, 0, 0, .5)" }
];

And this function to sort the array by name:

array.sort(function(a, b) {
  if (a.name < b.name) return -1;
  if (a.name > b.name) return 1;
  return 0;
});

And ECMAScript language specifications that tell me that:

The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order).

So, after sorting, the two items with name = background color could appear in any order i.e.:

[
  { name: "background-color", value: "rgb(0, 0, 0)" },
  { name: "background-color", value: "rgba(0, 0, 0, .5)" },
  ...
]

Or

[
  { name: "background-color", value: "rgba(0, 0, 0, .5)" },
  { name: "background-color", value: "rgb(0, 0, 0)" },
  ...
]

How can I sort the array so that items with same name maintain their relative order? I would rather not hardcode anything.

Improve this question
1

5 Answers 5

Reset to default
38

Theoretically before sorting you could keep track of its index in the array and take that into account when sorting.

var sortArray = yourarray.map(function(data, idx){
    return {idx:idx, data:data}
})

sortArray.sort(function(a, b) {
  if (a.data.name < b.data.name) return -1;
  if (a.data.name > b.data.name) return 1;
  return a.idx - b.idx
});

var answer = sortArray.map(function(val){
    return val.data
});
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

where do you get idx from?
Good catch, fixed the name of the arguments on the map function
@noveyak Since the array contains reference type objet, the index of the element can be determined in the sort function. So we avoid the map before and after the sort.
17

This changed as of ES2019, Array#sort is stable, meaning that the two entries with the same name will have the same position relative to one another as they did before the array was sorted:

22.1.3.27 Array.prototype.sort ( comparefn )

The elements of this array are sorted. The sort must be stable (that is, elements that compare equal must remain in their original order).

(my emphasis)

So in your case, the order of { name: "background-color", value: "rgb(0, 0, 0)" } and { name: "background-color", value: "rgba(0, 0, 0, .5)" } will remain the same, because they compare as equal.

Prior to ES2019, the sort wasn't required to be stable, so they could have had their order reversed — or not, depending on the implementation.

Stable sort is broadly supported (not least because most engines already implemented a stable sort, so there was nothing for them to do).

Improve this answer

1 Comment

Browser support table for stable sorting: caniuse.com/mdn-javascript_builtins_array_sort_stable
2

In ES6, if you cannot guarantee the sort order because of the browser environment or transpiler plugin set-up (in an ideal world, this shouldn't be a problem), a very idiomatic/quick approach could be:

values
 .map((v, i) => ([v,i]))
 .sort(([v1,i1], [v2,i2])=> (
     (v1==v2) ? (i2-i1) : (v2-v1)
)).map(([v,i])=>v); // or above flipped

The downside of this is it isn't quite as efficient as a merge sort, but it's pretty close since most browser implementations use it for Array.prototype.sort internally or even more optimal (and in this case should end up just being about O(2n) + O(nlogn)).

The upside is it's very convenient and easy to read -- imho 🙃

Improve this answer

Comments

1

Add an extra attribute to the array: order

var array = [
    { name: "border-color", value: "#CCCCCC", order: 1 },
    { name: "color", value: "#FFFFFF", order: 2 },
    { name: "background-color", value: "rgb(0, 0, 0)", order: 3 },
    { name: "background-color", value: "rgba(0, 0, 0, .5)", order: 4 }
];

and then change the sort function to sort on order if the name is equal:

array.sort(function(a, b) {
    if (a.name < b.name) return -1;
    if (a.name > b.name) return 1;
    if (a.name == b.name) {
        if(a.order > b.order) return -1; else return 1;
    }
});

Note that the sign of the return for the order has to be tweaked depending on whether you want it sorted increasing or decreasing (here, I assumed you're sorting from largest to smallest, so return the one with the smaller order).

Improve this answer

1 Comment

Using else is not needed, after a return statement. You can just do if(a.order > b.order) return -1; return 1; . You can also remove the wrapping if(a.name==b.name){} statement, which will always be true when executed (because it is neither > or <).
0

Since the array contains reference type objet, the index of the element can be determined in the sort function. So we avoid the map before and after the sort.

sortArray.sort((function(a, b) {
  if (a.name < b.name) return -1;
  if (a.name > b.name) return 1;
  return this.indexOf(a) - this.indexOf(b);
}).bind(sortArray));
Improve this answer

3 Comments

Wouldn't this be slow since it has to find the index every time?
sorry down-voted: this wouldn't be ok because this.indexOf(a) and this.indexOf(b) would change while sorting. You need to memorize the initial indexes before sorting
Adding with @ionescho, you will also have the wrong index returned by indexOf function, when you have multiple items with the same value in the array.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.