Best way to sort multidimentional array

Question

I have a multidimentional array

array = [];
array[0] = [1,3,8,4,9,5];
array[1] = [5,9,4,2,9,3,0];
array[2] = [5,2,6,1,3,8,4,9,5,17,2,9,3,0];
array[3] = [-1,0,20,6];

I want to sort it to get this result

[
       [-1,0,0,0,1,1],
       [2,2,2,3,3,3,3],
       [4,4,4,5,5,5,5,6,6,8,8,9,9,9],
       [9,9,17,20]
]

I have defined this function that helped me get this result

Array.prototype.sort_multi = function()
{
    var arr = [];
    this.forEach(function(element_arr,index_arr,array_arr)
    {
        element_arr.forEach(function(element,index,array)
        {
            arr.push(element);
        });
    });
    arr.sort(function (a, b) { return a - b;});
    this.forEach(function(element_arr,index_arr,array_arr)
    {
        element_arr.forEach(function(element,index,array)
        {
            array_arr[index_arr][index] = arr.shift();
        });
    });
    return this;
}

My question is: is there a simple way to do this ? for example using the function sort, or a simple algorithm ... ?

Join it, sort it, chunk it into pieces of the original size

Bergi
– Bergi

2014-07-26 15:50:14 +00:00
Commented Jul 26, 2014 at 15:50 — Bergi
– Bergi, Commented Jul 26, 2014 at 15:50

techfoobar · Accepted Answer · 2014-07-26 15:53:06Z

4

A slightly simplified (and slightly more efficient) version of sort_multi():

Basically what is happening here is:

The items in the original array are combined into one big array (for easy sorting)
We record the lengths of the original child arrays while joining
Sort the joined array numerically (as in the code you posted)
Split the sorted big array as per the lengths of the original child arrays
Return the result

Why this is more efficient than the original code:

The original code iterates through each child array element by element for joining. This is not needed since we have the natively implemented concat() for exactly that.
The original code again iterates element by element when splitting the joined/sorted array - Not needed since we have splice().

Array.prototype.sort_multi = function() {
    var joined = [], lens = [], result = [];
    this.forEach(function(item) {
        joined = joined.concat(item);
        lens.push(item.length); // store the initial lengths
    });
    joined = joined.sort(function (a, b) { return a - b;}); // sort numerically
    lens.forEach(function(item) { // for each length in lens
        result.push(joined.splice(0, item));
    });
    return result;
}

answered Jul 26, 2014 at 15:53

techfoobar

66.8k14 gold badges117 silver badges138 bronze badges

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

6 Comments

Bergi Over a year ago

Actually, your code with the repeated concats and splices is much less efficient than the original code. Can you fix that?

techfoobar Over a year ago

@Bergi - How is it less efficient.. It concats once for each child array and splices once for each child array expected in the output. So if you have 4 child arrays, it concats 4 times and splices 4 times. Can it be reduced? [Note: The method is to be called only on the parent array containing child arrays]

Bergi Over a year ago

Exactly. For 4 lists in the array, you create 4 joined arrays, and then do 4 splices, where each of these operations needs to iterate the whole array. It has O(n*n*m) complexity while it could be O(n*m)

techfoobar Over a year ago

Can you please post the suggested improvement in a fiddle perhaps. Maybe even as an answer as it will be helpful to future visitors. I'm out of ideas as to how to reduce it further.

techfoobar Over a year ago

Ok, concat can take any number of params, so one call should suffice. Still we'll need 4 splices. Right?

|

Collectives™ on Stack Overflow

Best way to sort multidimentional array

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related