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.
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
});
This changed recently. 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.
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).
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));
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
