How to Sort Complex Numerical multi-dimensional Javascript Array?

AnkitThummar
March 26, 2024
203 views
3 votes
3 Answers

I have to sort this array,

const array = [
  [18, [18, 16], 16],
  15,
  [18, 19, 51],
  [[18, 16], 15, [14, 13]],
  [10, 9, 20],
  99,
  49,
  [11, [22, 10], [[10, 9], 11, 9, [1, 2]], 100, 72],
  [[11], [[19, 14], [77, 18]]]
];

sort this array such that,

all single elements inside this array come first
after that one-dimensional arrays come second
after that two-dimensional arrays come third
after that three-dimensional arrays come fourth
…..so on
all elements should be sorted inside all the arrays.

Result should be like this,

[
  15,
  49,
  99,
  [18, 19, 51],
  [9, 10, 20],
  [16, 18, [16, 18]],
  [15, [16, 18], [13, 14]],
  [11, 72, 100, [10, 22], [9, 11, [9, 10], [1, 2]]],
  [[11], [[14, 19], [18, 77]]]
]

This is how I try to implement it – it is working for up to four-dimensional arrays, but this code will not work if we have n-dimensional array(were n>4), so how can we implement/optimise this code such that we can get result for all n-dimensional arrays.

const array = [
    [ 18, [18,16], 16], 
    15, 
    [18, 19, 51], 
    [[18, 16], 15, [14, 13]], 
    [10,9,20], 
    99, 
    49, 
    [11, [22,10], [[10,9], 11, 9, [1,2]], 100, 72],
    [[11], [[19, 14], [77, 18]]]
];

function getArrayDepth(value) {
    return Array.isArray(value) ?
        1 + Math.max(0, ...value.map(getArrayDepth)) :
        0;
}

function sort_array1(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                const temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

function sort_array2(arr) {
    for (let j = 0; j < arr.length; j++) {
        arr[j] = sort_array1(arr[j]);
    }

    return arr;
}

function sort_array3(arr) {
    for (let j = 0; j < arr.length; j++) {
        let array1 = [];
        let array2 = [];

        for (let k = 0; k < arr[j].length; k++) {
            if (getArrayDepth(arr[j][k]) == 0) {
                array1.push(arr[j][k]);
            }
            else {
                array2.push(arr[j][k]);
            }
        }

        array1 = sort_array1(array1);
        array2 = sort_array2(array2);
        arr[j] = array1.concat(array2);
    }

    return arr;
}

function sort_array4(arr) {
    for (let j = 0; j < arr.length; j++) {
        let array1 = [];
        let array2 = [];
        let array3 = [];

        for (let k = 0; k < arr[j].length; k++) {
            if (getArrayDepth(arr[j][k]) == 0) {
                array1.push(arr[j][k]);
            }
            else if (getArrayDepth(arr[j][k]) == 1) {
                array2.push(arr[j][k]);
            }
            else {
                array3.push(arr[j][k]);
            }
        }

        array1 = sort_array1(array1);
        array2 = sort_array2(array2);
        array3 = sort_array3(array3);
        arr[j] = array1.concat(array2, array3);
    }

    return arr;
}

function sequenced_array(arr) {
    let array1 = [];
    let array2 = [];
    let array3 = [];
    let array4 = [];

    for (let i = 0; i < arr.length; i++) {
        if (getArrayDepth(arr[i]) == 0) {
            array1.push(arr[i]);
        }
        else if (getArrayDepth(arr[i]) == 1) {
            array2.push(arr[i]);
        }
        else if (getArrayDepth(arr[i]) == 2) {
            array3.push(arr[i]);
        }
        else {
            array4.push(arr[i]);
        }
    }

    array1 = sort_array1(array1);
    array2 = sort_array2(array2);
    array3 = sort_array3(array3);
    array4 = sort_array4(array4);

    array1 = array1.concat(array2, array3, array4);
    return array1;
}

let sortedArray = sequenced_array(array);

/*for (let i = 0; i < sortedArray.length; i++) {
    console.log(sortedArray[i]);
}*/

console.log(sortedArray)

Answers

Chosen as BEST ANSWER

I solved this using recursion,

let complexArray = [
  [18, [18, 16], 16],
  15,
  [18, 19, 51],
  [[18, 16], 15, [14, 13]],
  [10, 9, 20],
  99,
  [[1, [20, [9, 3], 1], [90, 12], 90, 13], 26, [10, 2], 200, 100],
  49,
  [11, [22, 10], [[10, 9], 11, 9, [1, 2]], 100, 72],
  [
    [11],
    [
      [19, 14],
      [77, 18],
    ],
  ],
];

//Find the depth of the given array
function getArrayDepth(value) {
  return Array.isArray(value)
    ? 1 + Math.max(0, ...value.map(getArrayDepth))
    : 0;
}

function sortArray(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) {
        const temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

//Sort the complex array recursively
function sortComplexArray(arr) {
  //Declare a new array, inside this array we've to perform all operatins,
  //then we'll assign this array to our actual array.
  let newArray = [];
  let depth = getArrayDepth(arr);//Find the depth of the given array

  //According to depth of the all elements inside this array arrange them sequentially
  //ex,[single elements, two-dim, three-dim,..., n-dim]
  for (let d = 0; d <= depth; d++) {
    let tempArray = [];
    for (let i = 0; i < arr.length; i++) {
      if (getArrayDepth(arr[i]) == d) {
        tempArray.push(arr[i]);
      }
    }

    //If the given array is a one-dimensional array then sort that array
    if (d == 0) {
      tempArray = sortArray(tempArray);
    }
    newArray = newArray.concat(tempArray);
  }

  arr = newArray;

  //check that element is Array or not
  //if element is Array then pass that element into sortComplexArray
  for (let i = 0; i < arr.length; i++) {
    if (Array.isArray(arr[i])) {
      arr[i] = sortComplexArray(arr[i]);
    }
  }

  //after all this operations we've finally achieve our sorted array and we return it to caller
  return arr;
}

// Sort the complex array recursively
let sortedArray = sortComplexArray(complexArray);

// Output the sorted array
console.log(sortedArray);

Thanks! Everyone for your efforts to solve my question.

(Edit)

NOTE: The custom sort is quite heavy. This many have both a time and space complexity that may be prohibitive for very large and/or deep arrays.

Perhaps others may give a better solution

const getDepth = (item) => !Array.isArray(item) ? 0 : 1 + Math.max(...item.map(getDepth), 0);

const customSort = (a, b) =>  {
  const depthA = getDepth(a);
  const depthB = getDepth(b);
  if (depthA !== depthB) return depthA - depthB;
  if (Array.isArray(a) && Array.isArray(b)) {
    for (let i = 0; i < Math.min(a.length, b.length); i++) {
      const comp = customSort(a[i], b[i]);
      if (comp !== 0) return comp;
    }
    return a.length - b.length;
  }
  if (!Array.isArray(a) && !Array.isArray(b)) return a - b;
  return Array.isArray(a) ? 1 : -1;
}

const sortArray = (array) => {
  // only sort arrays
  if (!Array.isArray(array)) return array;

  // recursively sort arrays
  const deeplySorted = array.map(item => Array.isArray(item) ? sortArray(item) : item);

  // Then, sort by depth and value
  return deeplySorted.sort(customSort);
}

console.log(sortArray(array));

<script>
const array = [
    [18, [18, 16], 16],
    15,
    [18, 19, 51],
    [[18, 16], 15, [14, 13]],
    [10, 9, 20],
    99,
    49,
    [11, [22, 10], [[10, 9], 11, 9, [1, 2]], 100, 72],
    [[11], [[19, 14], [77, 18]]],
    [[[[3],[2],[2,3,1]]]] // Added this deeply nested array
];
</script>

scan to find array depths and clone the array (optional)
sort by calculated depths

const array = [
  [18, [18, 16], 16],
  15,
  [18, 19, 51],
  [[18, 16], 15, [14, 13]],
  [10, 9, 20],
  99,
  49,
  [11, [22, 10], [[10, 9], 11, 9, [1, 2]], 100, 72],
  [[11], [[19, 14], [77, 18]]]
];

const sortByDepth = (array, clone = true) => {

  const depths = new Map;

  const scan = arr => {
    let depth = 0;
    if(Array.isArray(arr)){
      depth = Math.max(...arr.map(scan));
      depths.set(arr, depth++);
    }
    return depth;
  };
  
  const scanClone = arr => {
    if(Array.isArray(arr)){
      const mapped = arr.map(scanClone);
      let {cloned, depth} = mapped.reduce((r, [arr, depth]) => (r.cloned.push(arr), r.depth < depth && (r.depth = depth), r), {cloned:[], depth:-Infinity});
      depths.set(cloned, depth++);
      return [cloned, depth];
    }
    return [arr, 0];
  };
  
  clone ? [array] = scanClone(array) : array.forEach(scan);

  const sort = arr => {
    arr.sort((a, b) => {
      const da = depths.get(a) ?? -1;
      const db = depths.get(b) ?? -1;
      if(da === -1 && db === -1){
        return a - b;
      }
      if(da > db) return 1;
      if(da < db) return -1;
      return 0;
    });
    arr.forEach(v => Array.isArray(v) && sort(v));
  }

  sort(array);
  return array;
}

sortByDepth(array).forEach(v => console.log(JSON.stringify(v)));

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

` Chrome/122
----------------------------------------------------------------------------
>                n=9       |      n=90      |     n=900      |    n=9000    
Alexander   1.00x x10k 122 | 1.00x  x1k 125 | 1.00x x100 134 | 1.00x x10 209
mplungan    3.89x x10k 474 | 8.80x x100 110 | 9.25x  x10 124 | 6.08x  x1 127
----------------------------------------------------------------------------
https://github.com/silentmantra/benchmark `

` Firefox/124
---------------------------------------------------------------------------
>                n=9       |     n=90      |     n=900      |    n=9000    
Alexander   1.00x x10k 152 | 1.00x x1k 150 | 1.00x x100 168 | 1.00x x10 224
mplungan    1.95x x10k 296 | 5.29x x1k 794 | 7.62x  x10 128 | 8.04x  x1 180
---------------------------------------------------------------------------
https://github.com/silentmantra/benchmark `

const $chunk = [
  [18, [18, 16], 16],
  15,
  [18, 19, 51],
  [[18, 16], 15, [14, 13]],
  [10, 9, 20],
  99,
  49,
  [11, [22, 10], [[10, 9], 11, 9, [1, 2]], 100, 72, [
      [18, [18, 16], 16],
      15,
      [18, 19, 51],
      [[18, 16], 15, [14, 13]],
      [10, 9, 20],
      99,
      49,
      [11, [22, 10], [[10, 9], 11, 9, [1, 2]], 100, 72],
      [[11], [[19, 14], [77, 18]]]
    ]],
  [[11], [[19, 14], [77, 18]]]
];

const $input = [];
const array = $input;

// @benchmark mplungan
const getDepth = (item) => !Array.isArray(item) ? 0 : 1 + Math.max(...item.map(getDepth), 0);

const customSort = (a, b) =>  {
  const depthA = getDepth(a);
  const depthB = getDepth(b);
  if (depthA !== depthB) return depthA - depthB;
  if (Array.isArray(a) && Array.isArray(b)) {
    for (let i = 0; i < Math.min(a.length, b.length); i++) {
      const comp = customSort(a[i], b[i]);
      if (comp !== 0) return comp;
    }
    return a.length - b.length;
  }
  if (!Array.isArray(a) && !Array.isArray(b)) return a - b;
  return Array.isArray(a) ? 1 : -1;
}

const sortArray = (array) => {
  // only sort arrays
  if (!Array.isArray(array)) return array;

  // recursively sort arrays
  const deeplySorted = array.map(item => Array.isArray(item) ? sortArray(item) : item);

  // Then, sort by depth and value
  return deeplySorted.sort(customSort);
}

// @run
sortArray(array);

// @benchmark Alexander

const sortByDepth = (array, clone = true) => {

  const depths = new Map;

  const scan = arr => {
    let depth = 0;
    if(Array.isArray(arr)){
      depth = Math.max(...arr.map(scan));
      depths.set(arr, depth++);
    }
    return depth;
  };
  
  const scanClone = arr => {
    if(Array.isArray(arr)){
      const mapped = arr.map(scanClone);
      let {cloned, depth} = mapped.reduce((r, [arr, depth]) => (r.cloned.push(arr), r.depth < depth && (r.depth = depth), r), {cloned:[], depth:-Infinity});
      depths.set(cloned, depth++);
      return [cloned, depth];
    }
    return [arr, 0];
  };
  
  clone ? [array] = scanClone(array) : array.forEach(scan);

  const sort = arr => {
    arr.sort((a, b) => {
      const da = depths.get(a) ?? -1;
      const db = depths.get(b) ?? -1;
      if(da === -1 && db === -1){
        return a - b;
      }
      if(da > db) return 1;
      if(da < db) return -1;
      return 0;
    });
    arr.forEach(v => Array.isArray(v) && sort(v));
  }

  sort(array);
  return array;
}
// @run
sortByDepth(array);

/*@skip*/ fetch('https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js').then(r => r.text().then(eval));

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

Please signup or login to give your own answer.

Click here to cancel reply.