Сортировка массива с помощью функции JavaScript JavaScript

Question

Часто я изучаю некоторые JavaScript вопросы интервью, внезапно я вижу вопрос об использовании reduce функции для сортировки Array, я читал об этом в MDN и об использовании в некоторые medium статьи, но сортировка Array настолько инновационная:

const arr = [91,4,6,24,8,7,59,3,13,0,11,98,54,23,52,87,4];

Я много думал, но не представляю, как ответить на этот вопрос, как должна быть функция reduce call back? что такое функция initialValue из reduce? и каковы accumulator и currentValue из call back функции reduce?

И, наконец, этот способ имеет некоторые преимущества по сравнению с другими алгоритмами сортировки? Или это полезно для улучшения других алгоритмов?

Answer 1

Вы можете использовать сортировку вставки:

let array        = [91, 4, 6, 24, 8, 7, 59, 3, 13, 0, 11, 98, 54, 23, 52, 87, 4];
let countIfLess  = (array,v)=> array.reduce((c,n)=>n<v?c+1:c,0);
let countIfEqual = (array,v)=> array.reduce((c,n)=>n==v?c+1:c,0);

console.log(
  array.reduce(
    (a,v,i,array)=>( a[countIfLess(array,v) + countIfEqual(a,v)]=v, a ),
    new Array(array.length)
  )
);

Это создаст массив назначения один раз, а затем выполнит вставку в него на каждом шаге сокращения без необходимости воссоздания массива назначения.

Существуют более эффективные способы реализации countIfEqual, но я решил реализовать все функции, используя reduce, а не другие функции массива.

Answer 2

Вот (imo) более элегантная версия решения сортировки вставок от Jonas W. Обратный вызов просто создает новый массив всех более низких значений, нового и всех более высоких значений. Избегает использования явных циклов или индексов, поэтому сразу видно, что он работает правильно.

const insertValue = (arr, value) =>
  [...arr.filter(n => n <= value), value, ...arr.filter(n => n > value)]

const testArr = [91, 4, 6, 24, 8, 7, 59, 3, 13, 0, 11, 98, 54, 23, 52, 87, 4]

console.log(testArr.reduce(insertValue, []))

Answer 3

reduce ограничивает себя алгоритмами онлайн-сортировки , где каждый элемент в массиве виден один раз, и вы не определяете заранее длину вашего массива (обратите внимание, что с помощью замыканий вы можете получить больше информации к восстановительной функции, но этот тип поражений цели вопроса).

сортировка вставок - очевидный и простой пример; Я не буду подробно описывать реализацию, так как другие ответы уже очень хороши в этом отношении. Однако вы можете упомянуть несколько оптимизаций, которые могут показаться интервьюеру очень позитивными:

• Использование бинарного поиска для нахождения точки вставки может снизить сложность шага вставки с O (n) до O (log n). Это называется двоичной сортировкой вставок: общее число сравнений будет идти от O (n ^ 2) до O (n log n). Это не будет быстрее, потому что реальная стоимость связана с «объединением» выходного массива, но если у вас были дорогие сравнения (например, сортировка длинных строк), это могло бы изменить ситуацию.

• Если вы сортируете целое число, вы можете использовать radix sort и реализовать алгоритм линейной онлайн-сортировки с помощью Reduce. Это довольно сложно реализовать, но очень подходит для сокращения.

Answer 4

Вы можете использовать некоторые функции для получения массива, если не указан массив, функция, которая возвращает отсортированный массив, принимая два параметра, и обратный вызов сортировки, который включает в себя вышеупомянутое, с использованием другого метода Reduce для получения результата части отсортированный массив.

const
    getArray = a => Array.isArray(a) ? a : [a],
    order = (a, b) => a < b ? [a, b] : [b, a],
    sort = (a, b) => getArray(a).reduce((r, v) => r.concat(order(r.pop(), v)), [b]),
    array = [91, 4, 6, 24, 8, 7, 59, 3, 13, 0, 11, 98, 54, 23, 52, 87, 4];

console.log(array.reduce(sort));

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

Answer 5

Array.sort изменяет массив, где использование Array.reduce поощряет чистую функцию. Вы можете клонировать массив перед сортировкой.

Я полагаю, что этот вопрос предназначен для того, чтобы заставить вас думать иначе, применяя ограничения. Он проверяет ваши знания о том, как работает reduce, и, как показывают ответы, существует много способов убрать кошку. Это покажет ваш личный вкус JS в решении этого.

Я решил использовать Array.findIndex и Array.splice.

const sortingReducer = (accumulator, value) => {
  const nextIndex = accumulator.findIndex(i => value < i );
  const index = nextIndex > -1 ? nextIndex : accumulator.length;
  accumulator.splice(index, 0, value);
  return accumulator;
}

const input = [5,4,9,1];
const output = input.reduce(sortingReducer, []);

Тестирование с вводом пробы дает

arr.reduce(sortingReducer, [])
// (17) [0, 3, 4, 4, 6, 7, 8, 11, 13, 23, 24, 52, 54, 59, 87, 91, 98]

Answer 6

Вот пример массива sorting в порядке убывания с использованием функции Reduce.

каково начальное значение функции уменьшения

В этой функции ниже начальным значением является [], которое передается как thisArg в функции уменьшения.

 array.reduce(function(acc,curr,currIndex,array){
        //rest of the code here
        },[]//this is initial value also known as thisArg)

Таким образом, в основном пустой массив передается, и элементы будут помещены в этот массив

Аккумулятором здесь является пустой массив.

const arr = [91, 4, 6, 24, 8, 7, 59, 3, 13, 0, 11, 98, 54, 23, 52, 87, 4];
var m = arr.reduce(function(acc, cur) {
  // this arrVar will have the initial array
  let arrVar = arr;
  // get the max element from the array using Math.max
  // ... is spread operator
  var getMaxElem = Math.max(...arrVar);
  // in the accumulator we are pushing the max value
  acc.push(getMaxElem);
  // now need to remove the max value from the array, so that next time it 
  // shouldn't not be considered
  // splice will return a new array
  // now the arrVar is a new array and it does not contain the current
  // max value
  arrVar = arrVar.splice(arrVar.indexOf(getMaxElem), 1, '')
  return acc;
}, []);
console.log(m)

Answer 7

Хотя сокращение не идеально предназначено для сортировки. Следующее решение похоже на forEach или любую функцию цикла, которая пытается быть достигнута с помощью функции Array.reduce.

var arr = [91,4,6,24,8,7,59,3,13,0,11,98,54,23,52,87,4];

arr = arr.reduce(function(acc,val){
  
  if(acc.length) {
    var temp = [];
    while(acc[acc.length -1] > val) {
      temp.push(acc.pop());
    } 
    acc.push(val);
    while(temp.length) {
      acc.push(temp.pop());
    }
  } else {
    acc.push(val);  
  }
  return acc;
  
}, []);

console.log(arr);

Обратите внимание, что вы можете использовать встроенную функцию Array.sort для сортировки, а также иметь собственную функцию сортировки, в которой вы можете определить собственный алгоритм сортировки.

Answer 8

Здесь нет смысла использовать Reduce, однако вы можете использовать новый массив в качестве аккумулятора и выполнить сортировку вставкой со всеми элементами:

array.reduce((sorted, el) => {
  let index = 0;
  while(index < array.length && el < array[index]) index++;
  sorted.splice(index, 0, el);
  return sorted;
}, []);

Вот версия без Reduce:

array.sort((a, b) => a - b);

---

Теперь несколько общих советов по написанию редукторов:

Каким должна быть функция сокращения обратного вызова?

Вы либо используете подход с аккумулятором, тогда редуктор должен применить модификацию к аккумулятору на основе текущего элемента и вернуть ее:

(acc, el) => acc

Или, если аккумулятор иэлементы имеют нормальный тип и логически равны, вам не нужно различать их:

 (a, b) => a + b

каково начальное значение функции Reduce?

Вы должны спросить себя «Что должно уменьшить возврат, когда он применяется к пустому массиву?»

Теперь самое важное: когдаиспользовать уменьшить?(IMO)

Если вы хотите свести значения массива к одному значению или объекту .