CODEWITHSUNDEEP
javascriptarrayssorting
Alice Polansky
Alice Polansky

Reputation: 3241

sort() doesn't work correctly in mozilla & opera

i need to sort one array but it works correctly only in Chrome. in the mozilla specification i found this text but nevertheless can't fix this:

"The elements of this array are sorted. The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order). If comparefn is not undefined, it should be a function that accepts two arguments x and y and returns a negative value if x < y, zero if x = y, or a positive value if x > y."

and this link https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Array/sort may be it will help you and me

this is my code

arr.sort(sortTrip); 

function sortTrip(a, b) {   

    if (a.to != b.from) return 1;
    if (a.to == b.from) return -1;

}

And this is the arr:

var arr = [
    {
        "from": "Moscow",
        "to": "Rome",
        "transport": "NSB Regiontog Train",
        "seat": "25"
    },
    {
        "from": "Oslo",
        "to": "Paris",
        "transport": "NSB Regiontog Train",
        "seat": "25"
    },
    {
        "from": "Helsinki",
        "to": "Tokio",
        "transport": "NSB Regiontog Train",
        "seat": "25"
    },
    {
        "from": "Tokio",
        "to": "Moscow",
        "transport": "NSB Regiontog Train",
        "seat": "25"
    },
    {
        "from": "Paris",
        "to": "New-York",
        "transport": "NSB Regiontog Train",
        "seat": "25"
    },
    {
        "from": "Rome",
        "to": "Oslo",
        "transport": "NSB Regiontog Train",
        "seat": "25"
    }
]

result must be

Upvotes: 0

Views: 452

Answers (2)

Bergi
Bergi

Reputation: 664538

See also Sorting in JavaScript: Should every compare function have a "return 0" statement?

if (a.to != b.from) return 1;
if (a.to == b.from) return -1;

That's not a consistent compare function (violating the reflexivity, i.e. compare(x, x) == 0, for example). What do you expect it to do?

Citing the ES5.1 spec on sort:

If comparefn is […] not a consistent comparison function for the elements of this array, the behaviour of sort is implementation-defined.

A function comparefn is a consistent comparison function for a set of values S if all of the requirements below are met for all values a, b, and c (possibly the same value) in the set S: The notation a <CF b means comparefn(a,b) < 0; a =CF b means comparefn(a,b) = 0 (of either sign); and a >CF b means comparefn(a,b) > 0.

Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments. Furthermore, Type(v) is Number, and v is not NaN. Note that this implies that exactly one of a <CF b, a =CF b, and a >CF b will be true for a given pair of a and b.

  • Calling comparefn(a,b) does not modify the this object.
  • a =CF a (reflexivity)
  • If a =CF b, then b =CF a (symmetry)
  • If a =CF b and b =CF c, then a =CF c (transitivity of =CF)
  • If a <CF b and b <CF c, then a <CF c (transitivity of <CF)
  • If a >CF b and b >CF c, then a >CF c (transitivity of >CF)

NOTE: The above conditions are necessary and sufficient to ensure that comparefn divides the set S into equivalence classes and that these equivalence classes are totally ordered.

Upvotes: 4

Bergi
Bergi

Reputation: 664538

My other answer explains why your sort does not work stable. This one will solve your actual problem :-)

You can't use a sort for this type of problem, where you want to construct a list of nodes from a (unordered) set of edges. Sorting an array is only applicable if you can compare two of the elements without additional data. Say you have only the two connections Tokio - Moscow and Rome - Oslo, you don't know which of them comes first (without contacting your plan, but you don't have that yet). In contrast, when comparing numbers you can easily and always tell that 5 is bigger than 3 (by computing the difference).

Instead, we need to do something like this or this - build a structure where we can easily access a station by name and insert connections directly when we encounter them during looping them, so that in the end we have a list of connections by station:

var map = {};
for (var i=0; i<arr.length; i++) {
    var con = arr[i];
    map[con.from] = con;
}

So that we can now construct your route as some kind of linked list:

for (var from in map) {
    var connTo = map[from].to;
    if (connTo in map)
        map[from].next = map[connTo];
}

And find the start station by deleting all destinations from the map:

for (var from in map)
    for (var next = map[from]; next; next = next.next)
         delete map[next.to];
for (from in map) // there's only one key left
    var start = from; // "Helsinki"

Let's construct the route as an array of station names:

var route = [start],
    conn = map[start];
while (conn) {
    route.push(conn.to)
    conn = conn.next;
    // maybe delete conn.next as we don't need it any more
}
// route:
// ["Helsinki", "Tokio", "Moscow", "Rome", "Oslo", "Paris", "New-York"]

or the result which you want, the list of connections:

var arr = [];
for (var conn = map[start]; conn; conn = conn.next)
    arr.push(conn);

Having that plan, we even could now construct a compare-function to sort the original array:

arr.sort(function(a, b) {
    // compare the positions of the departure stations in the route
    return route.indexOf(a.from) - route.indexOf(b.from);
});

Upvotes: 0

Related Questions