Javascript sort algorithm for linked sections objects array

Question

I have the following array of objects which need to be sorted in a special way:

var sections = [
    {begin:"test3", end:"test4"},
    {begin:"test5", end:"test2"},
    {begin:"test2", end:"test3"},
];

All sections are linked together via sectionA.end == sectionB.begin so the result of the sort operation should be:

var sectionsSorted = [
    {begin:"test5", end:"test2"},
    {begin:"test2", end:"test3"},
    {begin:"test3", end:"test4"}
];

I want to do this in the Array.prototype.sort() method. I realised that the beginning section could be found if the begin is not an end in any section but from there on I am lot. Has anybody an idea how to implement something like this?

I did a JSFiddle: https://jsfiddle.net/fxmnxh8L/1/

What defines the starting point of the new order? The largest begin? Or is there only one order fullfilling the conditions, and you have to serach the correct combination? Is the data guaranteed to contain an unbroken chain of the chainable values? — Teemu
– Teemu, Commented Nov 14, 2017 at 11:35
The starting point is defined by section.begin not in [all sections.end]. Hopefully I described it properly — perotom
– perotom, Commented Nov 14, 2017 at 11:39

Faly · Accepted Answer · 2017-11-14 12:48:23Z

3

Try this:

var sections = [
    {begin:"test3", end:"test4"},
    {begin:"test5", end:"test2"},
    {begin:"test2", end:"test3"},
];

sections.sort((s1, s2) => {
  return s1.end === s2.begin ? -1 : 1;
});

console.log(sections);

EDIT: the above solution doesn't work (see comments to know why). Take a look at the below solution that use a recursive approach to compare two given sections:

var sections = [    
    {begin: "test4", end: "test7"},
    {begin: "test5", end: "test2"},
    {begin: "test7", end: "test8"},
    {begin: "test2", end: "test3"},
    {begin: "test3", end: "test4"},
    {begin: "test8", end: "test9"}
];

var sectionsMap = sections.reduce((m, o) => {
    m[o.begin] = o;
    return m;
}, {});

function compare(a, b) {
    if (!sectionsMap[a.end]) {
        return 1;
    } else if (sectionsMap[a.end].begin === b.begin) {
        return -1;
    } else {
        return compare(sectionsMap[a.end], b);
    }
}

sections.sort(compare);

console.log(sections);

edited Nov 14, 2017 at 12:48

answered Nov 14, 2017 at 11:21

Faly

13.4k2 gold badges21 silver badges39 bronze badges

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

8 Comments

perotom Over a year ago

Looks great the only thing is test5 should be on the top. It is the first section

Faly Over a year ago

test5 is on the top

perotom Over a year ago

When I use the Run code snippet from Stackoverflow I get different result. I also tried it in the JSFiddle. Maybe it is not properly determining the overall beginning?

Faly Over a year ago

Try to change the callback return to: return s1.end === s2.begin ? -1 : s2.end === s1.begin ? 1 : 0;

Nina Scholz Over a year ago

you may try with more than 3 objects. thenproblem with this approach is, you have no relative order of two not connected objects. With valuse like numbers or strings, where a defined order is given, you actually don't know the order of some tokens.

|

Nina Scholz · Accepted Answer · 2017-11-14 11:58:46Z

1

You can not sort the array with Array#sort, because you need to have a stable sorting with defined predecessor, item and successor, which is not given, only if you view at two elements.

So you need a different approach by chaining all parts and get then the result out of the parts.

var sections = [{ begin: "test3", end: "test4" }, { begin: "test5", end: "test2" }, { begin: "test2", end: "test3" }],
    nodes = Object.create(null),
    begin = Object.create(null),
    end = Object.create(null),
    result;

sections.forEach(function (o) {
    nodes[o.begin] = o;
    begin[o.begin] = { a: [o.begin, o.end] };
    end[o.end] = begin[o.begin];

    if (begin[o.end]) {
        begin[o.end].a.unshift(o.begin);
        begin[o.begin] = begin[o.end];
        delete begin[o.end];
        delete end[o.end];
    }

    if (end[o.begin]) {
        Array.prototype.splice.apply(begin[o.begin].a, [0, 1].concat(end[o.begin].a));
        end[o.begin].a = begin[o.begin].a;
        delete begin[o.begin];
        delete end[o.end];
    }
    delete end[o.begin];
});

result = Object.keys(begin).map(function (k) {
    return begin[k].a.slice(0, -1).map(function (n) {
        return nodes[n];
    });
});

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

edited Nov 14, 2017 at 11:58

answered Nov 14, 2017 at 11:32

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

1 Comment

perotom Over a year ago

makes sense somehow. I also thought about a solution like that but thought it would be nice to have a solution without extra data structure. If I cannot find any other solution I will accept yours! Thanks!

Leo · Accepted Answer · 2017-11-14 11:29:03Z

0

try :

function compare(a,b) {
 if (a.end < b.end)
    return -1;
 if (a.end > b.end)
    return 1;
      }

sections.sort(compare);

https://jsfiddle.net/Micio/Lu3wqt0v/1/

answered Nov 14, 2017 at 11:29

Leo

6797 silver badges20 bronze badges

1 Comment

perotom Over a year ago

The problem is the sorting doesn't depend on the values of begin and end (I mean in terms of comparison. So a.end < b.end compares the values and not the linking. Simple example: jsfiddle.net/Lu3wqt0v/2 I exchanged the test2 <-> test3

Collectives™ on Stack Overflow

Javascript sort algorithm for linked sections objects array

3 Answers 3

8 Comments

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

8 Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related