Positional sort of 2d Array

Question

Problem

I have a 2d-array, which is actually data entered into Google Sheet. It is sorted by logic, defined by a user.

The goal is to enter new lines at the end of this table and then sort it by position.

Screen Shot

Saying "by position" I mean "Europe" goes before "America" because a user has entered it earlier.

Here is sample array for tests:

var data = 
  [
    ['Earth', 'Europe', 'Britain', 'London'],
    ['Earth', 'Europe', 'Britain', 'Manchester'],
    ['Earth', 'Europe', 'Britain', 'Liverpool'],
    ['Earth', 'Europe', 'France', 'Paris'],
    ['Earth', 'Europe', 'France', 'Lion'],
    ['Earth', 'Europe', 'Italy', 'Rome'],
    ['Earth', 'Europe', 'Italy', 'Milan'],
    ['Earth', 'Europe', 'Greece', 'Athenes'],
    ['Earth', 'Asia', 'China', 'Pekin'],
    ['Earth', 'Africa', 'Algeria', 'Algiers'],
    ['Earth', 'America', 'USA', 'Dallas'],
    ['Earth', 'America', 'USA', 'New York'],
    ['Earth', 'America', 'USA', 'Chicago'],
    ['Tatooine', 'Yulab', 'Putesh', 'ASU'],
    ['Tatooine', 'Yulab', 'Putesh', 'Niatirb'],
    ['Tatooine', 'Yulab', 'Zalip', 'Duantan'],
    ['Tatooine', 'Asia', 'Solo', 'Lion'],
    ['Tatooine', 'Asia', 'Solo', 'To'],
    ['Earth', 'America', 'USA', 'San Francisco'], 
    ['Tatooine', 'Yulab', 'Koko', 'Traiwau'],
    ['Venus', 'Yoo', 'Van', 'Derzar'],
    ['Tatooine', 'Chendoo', 'org', 'Eccel']
  ];

And correct resulting array is:

/*
  [  [Earth, Europe, Britain, London], 
     [Earth, Europe, Britain, Manchester], 
     [Earth, Europe, Britain, Liverpool], 
     [Earth, Europe, France, Paris], 
     [Earth, Europe, France, Lion], 
     [Earth, Europe, Italy, Rome], 
     [Earth, Europe, Italy, Milan], 
     [Earth, Europe, Greece, Athenes], 
     [Earth, Asia, China, Pekin], 
     [Earth, Africa, Algeria, Algiers], 
     [Earth, America, USA, Dallas], 
     [Earth, America, USA, New York], 
     [Earth, America, USA, Chicago], 
     [Earth, America, USA, San Francisco], 
     [Tatooine, Yulab, Putesh, ASU], 
     [Tatooine, Yulab, Putesh, Niatirb], 
     [Tatooine, Yulab, Zalip, Duantan], 
     [Tatooine, Yulab, Koko, Traiwau], 
     [Tatooine, Asia, Solo, Lion], 
     [Tatooine, Asia, Solo, To], 
     [Tatooine, Chendoo, org, Eccel], 
     [Venus, Yoo, Van, Derzar]
  ]
*/

I want to use a script for this.

My Solution

I've made my own version of a script, please see here:

https://github.com/Max-Makhrov/positional-sorting/blob/master/main.js

How the algorithm works

The algorithm finds groups starting from the first row: Earth > Europe > Britain. Then it tries to find a match for this groups in later entries.

I also thought about assigning higher indexes to earlier entries.

Question

The question: are there better approaches:

less code to accomplish the same task
More general ways to sort an array by position
Need fast enough solution, because I will use the code in sheets and it has limits on script time.

@Luca, I've edited the question and limited it to identify an adequate answer. Could you please reopen it. I've got the correct answer and hope my question would be helpful for other users — Max Makhrov, Oct 19 '17 at 06:11

Nina Scholz · Accepted Answer · 2017-10-19T11:06:32.640

You could use sorting with map, where every group gets the first found index for sorting the group.

Later take the last item for mapping back the array.

It works with a nested hash table for the groups, like

{
    Earth: {
        _: 0,
        Europe: {
            _: 0,
            Britain: {
                _: 0,
                London: {
                    _: 0
                },
                Manchester: {
                    _: 1
                },
                Liverpool: {
                    _: 2
                }
            },
            // ...
        },
        // ...
        America: {
            _: 10,
            USA: {
                _: 10,
                Dallas: {
                    _: 10
                },
                "New York": {
                    _: 11
                },
                Chicago: {
                    _: 12
                },
                "San Francisco": {
                    _: 18
                }
            }
        }
    }
}

where each property _ denotes the first index of the group.

The temporary array for sorting looks like this,

//    index of group
//        index of group
//            index of group
//                own index
[
    [  0,  0,  0,  0 ],
    [  0,  0,  0,  1 ],
    [  0,  0,  0,  2 ],
    [  0,  0,  3,  3 ],
    [  0,  0,  3,  4 ],
    [  0,  0,  5,  5 ],
    [  0,  0,  5,  6 ],
    [  0,  0,  7,  7 ],
    [  0,  8,  8,  8 ],
    [  0,  9,  9,  9 ],
    [  0, 10, 10, 10 ],
    [  0, 10, 10, 11 ],
    [  0, 10, 10, 12 ],  // /_        moving between
    [ 13, 13, 13, 13 ],  // \ |       both items
    [ 13, 13, 13, 14 ],  //   |
    [ 13, 13, 15, 15 ],  //   |/_
    [ 13, 16, 16, 16 ],  //   |\ |
    [ 13, 16, 16, 17 ],  //   |  |/_
    [  0, 10, 10, 18 ],  // --+  |\ |
    [ 13, 13, 19, 19 ],  // -----+  |
    [ 20, 20, 20, 20 ],  //         |
    [ 13, 21, 21, 21 ]   // --------+ 
]

This is taken for sorting the temporary array.

var data = [['Earth', 'Europe', 'Britain', 'London'], ['Earth', 'Europe', 'Britain', 'Manchester'], ['Earth', 'Europe', 'Britain', 'Liverpool'], ['Earth', 'Europe', 'France', 'Paris'], ['Earth', 'Europe', 'France', 'Lion'], ['Earth', 'Europe', 'Italy', 'Rome'], ['Earth', 'Europe', 'Italy', 'Milan'], ['Earth', 'Europe', 'Greece', 'Athenes'], ['Earth', 'Asia', 'China', 'Pekin'], ['Earth', 'Africa', 'Algeria', 'Algiers'], ['Earth', 'America', 'USA', 'Dallas'], ['Earth', 'America', 'USA', 'New York'], ['Earth', 'America', 'USA', 'Chicago'], ['Tatooine', 'Yulab', 'Putesh', 'ASU'], ['Tatooine', 'Yulab', 'Putesh', 'Niatirb'], ['Tatooine', 'Yulab', 'Zalip', 'Duantan'], ['Tatooine', 'Asia', 'Solo', 'Lion'], ['Tatooine', 'Asia', 'Solo', 'To'], ['Earth', 'America', 'USA', 'San Francisco'], ['Tatooine', 'Yulab', 'Koko', 'Traiwau'], ['Venus', 'Yoo', 'Van', 'Derzar'], ['Tatooine', 'Chendoo', 'org', 'Eccel']],
    hash = Object.create(null),
    result = data
        .map(function (a, i) {
            var temp = hash;
            return a.map(function (k) {
                temp[k] = temp[k] || { _: i };
                temp = temp[k];
                return temp._;
            });
        })
        .sort(function (a, b) {
            var value;
            a.some(function (v, i) {
                return value = v - b[i];
            });
            return value;
        })
        .map(function (indices) {
            return data[indices[indices.length - 1]];
        });

console.log(result.map(function (a) { return a.join(', '); }));

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

Thank you! This code is beautiful, but it gives me an alphabetical order, not positional. — Max Makhrov, Oct 18 '17 at 13:27
It means "Europe" goes before "America" because a user has entered it earlier. — Max Makhrov, Oct 18 '17 at 13:33
@MaxMakhrov How should the algorithm know which lines added later? Some of the not sorted ones might be logically sorted already. — serkan, Oct 18 '17 at 13:45
@ serkandemirel0420. The algorithm finds groups starting from the first row: Earth > Europe > Britain. Then it tries to find a match for this groups in later entries. I also thought about assigning higher indexes to earlier entries. — Max Makhrov, Oct 18 '17 at 13:55
@MaxMakhrov, please see edit, it sorts now by first sorted groups. — Nina Scholz, Oct 18 '17 at 17:15

Positional sort of 2d Array

Problem

My Solution

How the algorithm works

Question

1 Answers1