Какой самый быстрый способ объединить N несортированных массивов в 1 отсортированный массив в JavaScript? - PullRequest
Новая
       74

Какой самый быстрый способ объединить N несортированных массивов в 1 отсортированный массив в JavaScript?

0 голосов
/ 20 февраля 2020

У меня проблемы с объединением N несортированных массивов в 1 отсортированный массив в JavaScript.

Я знаю, что могу быстро объединить, а затем отсортировать, но здесь важна эффективность.

У меня есть массивы, которые я получаю от API (я не могу гарантировать, что они прибывают отсортированными), которые нуждаются в конечном итоге в 1 отсортированный массив. Моим первым инстинктом было попытаться не изобретать велосипед и попытаться найти способ надежной сортировки их в выходной массив. Я решил, что попробую отсортировать каждый из них, а затем использовать алгоритм на GeeksForGeeks . Это требует, чтобы массивы были в отсортированном порядке, поэтому я сначала сортирую массивы индивидуально

Я не провел много времени в C ++, поэтому я потратил некоторое время, пытаясь переопределить это в JavaScript: 

const TinyQueue = require('tinyqueue'); // const Heap = require('heap');

//typedef pair<int, pair<int, int> > ppi; 
const pair = (val1, val2) => ({ first: val1, second: val2 });
const ppi = (val1, [val2a, val2b]) => pair(val1, pair(val2a, val2b));
//console.log(ppi('a', ['b', 'c'])) -> { first: 'a', second: { first: 'b', second: 'c' } }

// This function takes an array of arrays as an 
// argument and all arrays are assumed to be 
// sorted. It merges them together and prints 
// the final sorted output.  
function mergeKArrays(arr) {
  const output = [];
  queue = new TinyQueue();

  for (var i = 0, len = arr.length; i < len; i++) queue.push(ppi(arr[i][0], [i, 0]));

  while(queue.length) {
    let curr = queue.pop();
    // i ==> Array Number 
    // j ==> Index in the array number   
    let i = curr.second.first;   
    let j = curr.second.second;

    output.unshift(curr.first); 

    // The next element belongs to same array as current. 
    if (j + 1 < arr[i].length) queue.push(ppi( arr[i][j + 1], [ i, j + 1]));
  }

  return output;
}
// -- Test Data --
const unsortedArrays = [
  [12, 2, 6], 
  [9, 1], 
  [2000, 23, 34, 90]
];
const sortedArrays = unsortedArrays.map(array => array.sort((a,b) => a - b));

console.log(sortedArrays);
const mergedArr = mergeKArrays(sortedArrays);

console.log(mergedArr);

Алгоритм Geeks for Geeks . Этот код используется в repl.it .

Таким образом, ввод [ [ 2, 6, 12 ], [ 1, 9 ], [ 23, 34, 90, 2000 ] ]

Ожидаемый вывод [ 1, 2, 6, 9, 12, 23, 34, 90, 2000 ]

Фактический вывод [ 9, 2000, 1, 90, 12, 34, 6, 23, 2 ]

Что здесь не так? Если это сработало, есть ли более эффективный способ объединить N несортированных массивов в 1 отсортированный?

Ответы [ 2 ]

0 голосов
/ 20 февраля 2020

V8 использует Timsort , который использует естественные пробеги. Таким образом, вы можете сортировать и сортировать: 

const unsortedArrays = [
  [12, 2, 6], 
  [9, 1], 
  [2000, 23, 34, 90]
];
const sorted = unsortedArrays.flat().sort((a, b) => a - b);
console.info(sorted);
0 голосов
/ 20 февраля 2020

Я бы сначала сгладил массив, а затем отсортировал 

 let input = [ [ 2, 6, 12 ], [ 1, 9 ], [ 23, 34, 90, 2000 ] ];
 let output = input.reduce((complete, next) => complete.concat(next), []) // to flatten
      .sort((a,b) => a-b) //to sort

в соответствии с этой статьей для больших массивов. Механизм Google V8 использует Quicksort, что занимает примерно O (n.log (п))

...