# Problem sorting a two-dimensional array

I am declaring a 2D array like this…

``````var myArray = [];
myArray[0] = [];
myArray[1] = [];
``````

So now the first dimension will have a size of two (0 or 1) and the second dimension will have an unlimited size.

I want to sort this array by the integer values held in myArray[1], where x is any number between zero and the size of my result set. That is, I want to reorder the array such that

myArray[1][0] >= myArray[1][1] >= myArray[1][2] >= myArray[1][3], etc.

All of the sorting functions I’ve found do something like this…

``````myArray.sort(mySorting);
``````

where mySorting is a function such as the one below…

``````function mySorting(a,b) {
a = a[1];
b = b[1];
return a == b ? 0 : (a < b ? -1 : 1)
}
``````

The problem I am having is that this mechanism sorts the wrong dimension! It is expecting my array matrix to be organized like this:

myArray[0][0] myArray[0][1]
myArray[1][0] myArray[1][1]
myArray[2][0] myArray[2][1]
myArray[3][0] myArray[3][1]

when in fact, my matrix looks like this…

myArray[0][0] myArray[1][0]
myArray[0][1] myArray[1][1]
myArray[0][2] myArray[1][2]
myArray[0][3] myArray[1][3]

Consequently, the sorting function mySorting does not work because instead of comparing myArray[1][0] to myArray[1][1], it is comparing myArray[0][1] to myArray[1][1]. That is, instead of sorting all of the values in my second column, it is sorting the two columns of just the second row.

This seems like it should be very simple but for some reason, I’m having difficulty figuring out how to either rewrite the function or change the way I am declaring my arrays.

I would be delighted if someone could set me straight here on my understanding of javascript arrays.

Thanks!

Is this what you’re after? Where if the sort values are an array, the arrays are themself sorted?

``````
Before:
[0][0] 0 [1][0] 7
[0][1] 9 [1][1] 1
[0][2] 3 [1][2] 0
[0][3] 3 [1][3] 1
[0][4] 0 [1][4] 6
[0][5] 5 [1][5] 7
[0][6] 6 [1][6] 6

After:
[0][0] 0 [1][0] 0
[0][1] 0 [1][1] 1
[0][2] 3 [1][2] 1
[0][3] 3 [1][3] 6
[0][4] 5 [1][4] 6
[0][5] 6 [1][5] 7
[0][6] 9 [1][6] 7

``````

The following sort is what sorts as above.

``````
function mySorting(a,b) {
if (isArray(a)) {
a.sort(mySorting);
b.sort(mySorting);
} else {
return a == b ? 0 : (a < b ? -1 : 1);
}
}

``````

Here’s the full test code, which was badly hacked together and also includes many horrible document.write statements.
Enjoy.

``````
function isArray(obj) {
if (!obj) {
return false;
}
if (obj.constructor.toString().indexOf("Array") == -1) {
return false;
} else {
return true;
}
}

function show(array) {
for (j = 0; j < 7; j += 1) {
for (i = 0; i < 2; i += 1) {
document.write('[' + i + '][' + j + ']' + ' ' + array[i][j] + ' ');
}
document.write('<br>');
}
}

var myArray = [];
for (i = 0; i < 2; i += 1) {
myArray[i] = [];
for (j = 0; j < 7; j += 1) {
myArray[i][j] = parseInt(Math.random() * 10, 10);
}
}

document.write('Before:<br>');
show(myArray);
document.write('<br>');

function mySorting(a,b) {
if (isArray(a)) {
a.sort(mySorting);
b.sort(mySorting);
} else {
return a == b ? 0 : (a < b ? -1 : 1);
}
}

myArray.sort(mySorting);

document.write('After:<br>');
show(myArray);

``````

Hi PMW, Many thanks for this excellent and thoughtful reply. A nice explanation of this approach. The jquery plugin I noted performed flawlessly so I left it in place. But I’ll implement your solution when I’m next confronted with this problem. Thanks again!

Oh yeah. On closer inspection, I see why your mySorting function is not infinitely recursive. The isArray test simply strips out dimensions until there are none left.

Another way to deal with this is to restructure the array for sorting purposes, and then once sorted to restructure again back to the original array.

Because we’ll want to check further info when an identical match occurs, let’s rework the sort function so that instead of checking one number against another, it instead accepts the whole row and checks the last items. If it comes across identical values it can then check the next from last, so so forth.

Let us sort these two arrays, so that when sorting according to the last column at 4, the bottom array ends up on the top due to the values in the first column.

``````
[9, 5, 0, 3]
[5, 5, 0, 3]

``````

The first array goes in to our sorting function as arrayA, and the second array goes in as arrayB.

Our sorting function compares the last value of each array, and when they’re the same it then steps left to the next-from-last and compares those. Whenever it comes across an identical match, it steps left and compares again.

That is how our sorting algorithm must work.

In order for our sorting algorithm to work like that, the array that is being sorted must be accessed as [row][col].

If the array that you want to sort is [col][row] then you must transpose it to a new array as [row][col], sort that, then transpose the sorted array back to the original array as [col][row]

Because your matrix is [col][row] you need to perform those extra transposition steps, since it’s not feasible for the sorting technique to work when they are the other way around.

Let’s start with creating an array using [col][row] ordering, so that we can show the result.

``````
function show(array) {
var col, row;
for (row = 0; row < array[0].length; row += 1) {
for (col = 0; col < array.length; col += 1) {
document.write('[' + col + '][' + row + ']' + ' ' + array[col][row] + ' ');
}
document.write('<br>');
}
}

var myArray = [];
for (col = 0; col < 4; col += 1) {
myArray[col] = [];
for (row = 0; row < 7; row += 1) {
myArray[col][row] = parseInt(Math.random() * 10, 10);
}
}

document.write('Before:<br>');
show(myArray);
document.write('<br>');

``````

Our customSort function needs to transpose the array, sort it, then return a retransposed version of the sorted array.

``````
function customSort(array) {
var transposed = transpose(array);
transposed.sort(byLastUniqueItem);
return transpose(transposed);
}

myArray = customSort(myArray);

``````

Here’s the transpose function:

``````

function transpose(array) {
// Transposes a two-dimensional array so that
// array[col][row] is returned as array[row][col]
var transposed = [],
row,
col;
for (row = 0; row < array[0].length; row += 1) {
transposed[row] = [];
for (col = 0; col < array.length; col += 1) {
transposed[row][col] = array[col][row];
}
}
return transposed;
}

``````

And here’s the byLastUniqueItem function, which allows us to walk backwards through each array if there’s an identical match:

``````

function byLastUniqueItem(arrayA, arrayB) {
var index = arrayA.length,
a,
b,
direction = 0;
while (direction === 0 && index >= 0) {
index -= 1;
a = arrayA[index];
b = arrayB[index];
direction = (a == b ? 0 : (a < b ? -1 : 1));
}
return direction;
}

``````

Here’s how it works where even nearly all items in a row are the same:

``````
Before:
[0][0] 6 [1][0] 4 [2][0] 6 [3][0] 2
[0][1] 9 [1][1] 8 [2][1] 5 [3][1] 0
[0][2] 8 [1][2] 5 [2][2] 0 [3][2] 8
[0][3] 0 [1][3] 6 [2][3] 3 [3][3] 4
[0][4] 9 [1][4] 5 [2][4] 0 [3][4] 3
[0][5] 4 [1][5] 7 [2][5] 3 [3][5] 6
[0][6] 5 [1][6] 5 [2][6] 0 [3][6] 3

After:
[0][0] 9 [1][0] 8 [2][0] 5 [3][0] 0
[0][1] 6 [1][1] 4 [2][1] 6 [3][1] 2
[0][2] 5 [1][2] 5 [2][2] 0 [3][2] 3
[0][3] 9 [1][3] 5 [2][3] 0 [3][3] 3
[0][4] 0 [1][4] 6 [2][4] 3 [3][4] 4
[0][5] 4 [1][5] 7 [2][5] 3 [3][5] 6
[0][6] 8 [1][6] 5 [2][6] 0 [3][6] 8

``````

And here’s the full test code:

``````
function show(array) {
var col, row;
for (row = 0; row < array[0].length; row += 1) {
for (col = 0; col < array.length; col += 1) {
document.write('[' + col + '][' + row + ']' + ' ' + array[col][row] + ' ');
}
document.write('<br>');
}
}

function transpose(array) {
// Transposes a two-dimensional array so that
// array[col][row] is returned as array[row][col]
var transposed = [],
row,
col;
for (row = 0; row < array[0].length; row += 1) {
transposed[row] = [];
for (col = 0; col < array.length; col += 1) {
transposed[row][col] = array[col][row];
}
}
return transposed;
}

function byLastUniqueItem(arrayA, arrayB) {
var index = arrayA.length,
a,
b,
direction = 0;
while (direction === 0 && index >= 0) {
index -= 1;
a = arrayA[index];
b = arrayB[index];
direction = (a == b ? 0 : (a < b ? -1 : 1));
}
return direction;
}

function customSort(array) {
var transposed = transpose(array);
transposed.sort(byLastUniqueItem);
return transpose(transposed);
}

var myArray = [];
for (col = 0; col < 4; col += 1) {
myArray[col] = [];
for (row = 0; row < 7; row += 1) {
myArray[col][row] = parseInt(Math.random() * 10, 10);
}
}

document.write('Before:<br>');
show(myArray);
document.write('<br>');

myArray = customSort(myArray);

document.write('After:<br>');
show(myArray);

``````

Many thanks for your reply, PMW. I’m sorry if I wasn’t clear. I want to sort by the second column only, while maintaining first and second column pairings. That is,

Before:
[0][0] 0 [1][0] 7
[0][1] 9 [1][1] 1
[0][2] 3 [1][2] 0
[0][3] 3 [1][3] 1
[0][4] 0 [1][4] 6
[0][5] 5 [1][5] 7
[0][6] 6 [1][6] 6

After:
[0][0] 3 [1][0] 0
[0][1] 9 [1][1] 1
[0][2] 3 [1][2] 1
[0][3] 0 [1][3] 6
[0][4] 6 [1][4] 6
[0][5] 0 [1][5] 7
[0][6] 5 [1][6] 7

I’ll test your code later to see how I can modify it to get the results I need. Your recursive function is interesting. Why is it not infinitely recursive? In the meantime, I found an impressive jquery pluggin (http://tablesorter.com) that allows table columns to be sorted by clicking the column header (more than I need but a great feature) but also provides for an initial sorting-by-column (all I’m trying to accomplish here). I already have it working in my code but I will revisit your code soon because I prefer the leaner approach.

Thanks!

Ignore this post. This post can be considered a thought experiment, to help work out what ways are more effective than others.

I repeat, ignore this post. There is a much better solution below it.[/edit]

Given that you have a two dimensional array, where the first dimension has two items, and the second dimension has a certain number of other items, the sort function will always start off by trying to sort according to the first dimension.

If we are to ensure that the items from index 0 are to be sorted in the same manner as those in index 1, we need to either connect them in some way so that they both are sorted as the same time, or we need to record where each one is so that the moves can be duplicated.

Both seem like a lot of work, but the latter one seems like it might be easier.

How recursive are you going to want this? What sorts of dimensions do you intend for this to work with. The more flexible you want it, the trickier it can get to code up.

Currently, it sorts any two-dimensional array according to the last column of the array.

We can saves the sorting decisions to a global array, which can then be retrieved and replayed when sorting the rest of the array throughout the mySorting function.

``````
function setSortDirection(a, b) {
var direction = (a == b ? 0 : (a < b ? -1 : 1));
window.sortOrder.push(direction);
return direction;
}

function mySorting(a, b) {
var direction = window.sortOrder.shift(); // get first item from array
window.sortOrder.push(direction); // put it back on at the end of the array
return direction;
}

``````

Here’s how the sorting is put together:

``````
function customSort(array) {
window.sortOrder = [];
var lastItem = array.length - 1,
i;

array[lastItem].sort(setSortDirection);
for (i = 0; i < array.length - 1; i += 1) {
array[i].sort(mySorting);
}
}

``````

With a 4x7 array, here’s how it’s sorted according to the last column:

``````Before:
[0][0] 8 [1][0] 4 [2][0] 9 [3][0] 3
[0][1] 4 [1][1] 7 [2][1] 9 [3][1] 7
[0][2] 6 [1][2] 9 [2][2] 3 [3][2] 9
[0][3] 2 [1][3] 4 [2][3] 7 [3][3] 7
[0][4] 8 [1][4] 6 [2][4] 1 [3][4] 3
[0][5] 6 [1][5] 6 [2][5] 5 [3][5] 6
[0][6] 2 [1][6] 7 [2][6] 6 [3][6] 3

After:
[0][0] 8 [1][0] 4 [2][0] 9 [3][0] 3
[0][1] 8 [1][1] 6 [2][1] 1 [3][1] 3
[0][2] 2 [1][2] 7 [2][2] 6 [3][2] 3
[0][3] 6 [1][3] 6 [2][3] 5 [3][3] 6
[0][4] 4 [1][4] 7 [2][4] 9 [3][4] 7
[0][5] 2 [1][5] 4 [2][5] 7 [3][5] 7
[0][6] 6 [1][6] 9 [2][6] 3 [3][6] 9

``````

As you can see, it’s mostly right, apart from when the last column has equal matches. That might be resolved by checking for a sort direction of 0 and working further back through the array, but with the way things are currently being done that would mean more complex code.

Here’s the test code that produces the above results:

``````

function show(array) {
for (j = 0; j < array[0].length; j += 1) {
for (i = 0; i < array.length; i += 1) {
document.write('[' + i + '][' + j + ']' + ' ' + array[i][j] + ' ');
}
document.write('<br>');
}
}

function setSortDirection(a, b) {
var direction = (a == b ? 0 : (a < b ? -1 : 1));
window.customSort.order.push(direction);
return direction;
}

function mySorting(a, b) {
var direction = window.customSort.order.shift(); // get first item from array
window.customSort.order.push(direction); // put it back on at the end of the array
return direction;
}

function customSort(array) {
window.customSort.order = [];
var lastItem = array.length - 1,
i;

array[lastItem].sort(setSortDirection);
for (i = 0; i < array.length - 1; i += 1) {
array[i].sort(mySorting);
}
}

var myArray = [];
for (i = 0; i < 4; i += 1) {
myArray[i] = [];
for (j = 0; j < 7; j += 1) {
myArray[i][j] = parseInt(Math.random() * 10, 10);
}
}

document.write('Before:<br>');
show(myArray);
document.write('<br>');

customSort(myArray);

document.write('After:<br>');
show(myArray);

``````

Further investigation is definitely required on this.