Alice Polansky Alice Polansky - 6 months ago 14
Javascript Question

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


  • Helsinki - Tokio

  • Tokio - Moscow

  • Moscow - Rome

  • Rome - Oslo

  • Oslo - Paris

  • Paris - New-York


Answer

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);
});