Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How does one sort a multi dimensional array by multiple columns in JavaScript?

I've been working on this problem all day without a good solution. Google has been little help as well. I have a script that needs to accept a two dimensional array with an unknown number number of rows/columns. The script also needs to accept a one dimensional array containing a list of columns to sort by, and another containing the order to sort by. The call will look a little like this:

var orderList = {0,4,3,1};
var orderDir = {asc,desc,desc,asc};
dataArr = do2DArraySort(dataArr, orderList, orderDir);

The function do2DArraySort should return the dataArr array sorted by the first column (in ascending order), then by the fifth (in descending order), then by the third (in descending order), then by the second (in descending order). I was able to make it two levels deep using the code below, but it fell apart once I tried adding a third sort column. I understand why, but I can't figure out a good way to make it work.

Is there a standard way of doing this? Could someone point me to a good script online I can study and use as a template? Or can someone suggest a modification to my code to make it work?

Thanks!

//appends an array content to the original array
function addToArray(originalArray, addArray) {
    if (addArray.length != 0) {
        var curLength = 0;
        curLength = originalArray.length;
        var maxLength = 0;
        maxLength = curLength + addArray.length;  
        var itrerateArray = 0;
        for (var r = curLength; r < maxLength; r++) {   
            originalArray[r] = addArray[itrerateArray];
            itrerateArray++;
        }
    }
}

function do2DArraySort(arrayToBeSorted, sortColumnArray, sortDirectionArray) {
    if (arrayToBeSorted == "undefined" || arrayToBeSorted == "null") return arrayToBeSorted;
    if (arrayToBeSorted.length == 0) return arrayToBeSorted;
    if (sortColumnArray.length == 0) return arrayToBeSorted;
    tempArray = arrayToBeSorted; 
    var totalLength = sortColumnArray.length; 
    for(var m = 0; m < totalLength; m++) {
        if (m == 0) {   
            doBubbleSort(tempArray, tempArray.length, sortColumnArray[m], sortDirectionArray[m]);         
        } else {     
            doMultipleSort(tempArray, sortColumnArray[m], sortColumnArray[m-1], sortDirectionArray[m]);
        }
    } 
    return tempArray;
}

//check if a value exists in a single dimensional array
function checkIfExists(arrayToSearch, valueToSearch) {
    if (arrayToSearch == "undefined" || arrayToSearch == "null") return false;
    if (arrayToSearch.length == 0) return false;
    for (var k = 0; k < arrayToSearch.length; k++) {
        if (arrayToSearch[k] == valueToSearch) return true;
    }
    return false;
}

//sorts an 2D array based on the distinct values of the previous column
function doMultipleSort(sortedArray, currentCol, prevCol, sortDirection) {
    var resultArray = new Array(); 
    var newdistinctValuesArray = new Array();
    //finding distinct previous column values 
    for (var n = 0; n < sortedArray.length; n++) {
        if (checkIfExists(newdistinctValuesArray, sortedArray[n][prevCol]) == false) newdistinctValuesArray.push(sortedArray[n][prevCol]);
    }
    var recCursor = 0;
    var newTempArray = new Array(); var toStoreArray = 0; 
    //for each of the distinct values
    for (var x = 0; x < newdistinctValuesArray.length; x++) {
        toStoreArray = 0;
        newTempArray = new Array();  
        //find the rows with the same previous column value
        for (var y = 0; y < sortedArray.length; y++) {
            if (sortedArray[y][prevCol] == newdistinctValuesArray[x]) {
                newTempArray[toStoreArray] = sortedArray[y];
                toStoreArray++;
            }
        }       //sort the row based on the current column
        doBubbleSort(newTempArray, newTempArray.length, currentCol, sortDirection);
        //append it to the result array
        addToArray(resultArray, newTempArray);
    }
    tempArray = resultArray;
}
like image 255
Nicholas Avatar asked May 23 '11 18:05

Nicholas


2 Answers

There are already good answers to this question, would like to add a short functions to handle multiple key array sort inspired solution of https://stackoverflow.com/users/2279116/shinobi.

// sort function handle for multiple keys
const sortCols  = (a, b, attrs) => Object.keys(attrs)
    .reduce((diff, k) =>  diff == 0 ? attrs[k](a[k], b[k]) : diff, 0);

Let's take an following example

const array = [
    [1, 'hello', 4],
    [1, 'how', 3],
    [2, 'are', 3],
    [1, 'hello', 1],
    [1, 'hello', 3]
];

array.sort((a, b) => sortCols(a, b, { 
   0: (a, b) => a - b, 
   1: (a, b) => a.localeCompare(b), 
   2: (a, b) => b - a
}))

The output would be following.

[ 1, "hello", 4 ]​
[ 1, "hello", 3 ]​
[ 1, "hello", 1 ]​
[ 1, "how", 3 ]
​[ 2, "are", 3 ]
like image 200
rab Avatar answered Nov 18 '22 03:11

rab


The array literal [] is preferred over new Array. The notation {0,4,3,1} is not valid and should be [0,4,3,1].

Is there a need for reinventing the wheel? Two arrays can be joined using:

originalArray = originalArray.concat(addArray);

Elements can be appended to the end using:

array.push(element);

Arrays have a method for sorting the array. By default, it's sorted numerically:

// sort elements numerically
var array = [1, 3, 2];
array.sort(); // array becomes [1, 2, 3]

Arrays can be reversed as well. Continuing the previous example:

array = array.reverse(); //yields [3, 2, 1]

To provide custom sorting, you can pass the optional function argument to array.sort():

array = [];
array[0] = [1, "first element"];
array[1] = [3, "second element"];
array[2] = [2, "third element"];
array.sort(function (element_a, element_b) {
    return element_a[0] - element_b[0];
});
/** array becomes (in order):
 * [1, "first element"]
 * [2, "third element"]
 * [3, "second element"]
 */

Elements will retain their position if the element equals an other element. Using this, you can combine multiple sorting algoritms. You must apply your sorting preferences in reverse order since the last sort has priority over previous ones. To sort the below array by the first column (descending order) and then the second column (ascending order):

array = [];
array.push([1, 2, 4]);
array.push([1, 3, 3]);
array.push([2, 1, 3]);
array.push([1, 2, 3]);
// sort on second column
array.sort(function (element_a, element_b) {
    return element_a[1] - element_b[1];
});
// sort on first column, reverse sort
array.sort(function (element_a, element_b) {
    return element_b[0] - element_a[0];
});
/** result (note, 3rd column is not sorted, so the order of row 2+3 is preserved)
 * [2, 1, 3]
 * [1, 2, 4] (row 2)
 * [1, 2, 3] (row 3)
 * [1, 3, 3]
 */

To sort latin strings (i.e. English, German, Dutch), use String.localeCompare:

array.sort(function (element_a, element_b) {
    return element_a.localeCompare(element_b);
});

To sort date's from the Date object, use their milliseconds representation:

array.sort(function (element_a, element_b) {
    return element_a.getTime() - element_b.getTime();
});

You could apply this sort function to all kind of data, just follow the rules:

x is the result from comparing two values which should be returned by a function passed to array.sort.

  1. x < 0: element_a should come before element_b
  2. x = 0: element_a and element_b are equal, the elements are not swapped
  3. x > 0: element_a should come after element_b
like image 26
Lekensteyn Avatar answered Nov 18 '22 04:11

Lekensteyn