Positional sort of 2d Array [closed]

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.

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:

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

Answer 1

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