por - Ordenar Array con función de reducción de JavaScript

sort numbers javascript

Question

A menudo estudio algunas preguntas de la entrevista de JavaScript , de repente vi una pregunta sobre el uso de reduce función de reduce para clasificar un Array , leí sobre esto en MDN y sobre su uso en algunos artículos medium , pero clasificar un Array es tan innovador:

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

Pensé mucho, pero no tengo idea de cómo responder a esta pregunta, ¿cómo debe ser la función de reduce call back ? ¿ initialValue es el valor initialValue de reduce función de reduce ? y ¿cuáles son el accumulator y el valor currentValue de call back función de currentValue de call back de reduce ?

Y al final, ¿Tiene esta manera algunos beneficios que otros algoritmos de clasificación? ¿O es útil mejorar otros algoritmos?

Answer 1

Aquí hay una (imo) versión más elegante de la solución de ordenación por inserción de Jonas W. La devolución de llamada simplemente crea una nueva matriz de todos los valores más bajos, el nuevo y todos los valores más altos. Evita el uso de bucles o índices explícitos, por lo que es más fácil ver de un vistazo que funciona correctamente.

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 2

Este es un ejemplo de la sorting una matriz en orden descendente utilizando la función de reducción.

¿Cuál es el valor inicial de la función de reducción?

En esta función a continuación, el valor inicial es el [] que se pasa como thisArg en la función de reducción.

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

Así que básicamente se pasa una matriz vacía y los elementos se insertarán en esta matriz

El acumulador aquí es la matriz vacía.

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 3

No tiene sentido usar Reducir aquí, sin embargo, podría usar una nueva matriz como acumulador y hacer una clasificación por inserción con todos los elementos:

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

Aquí está la versión sin reducir:

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

Ahora algunos consejos generales para escribir reductores:

¿Cómo debe ser la función de reducción de devolución de llamada?

O bien adopta un enfoque con un acumulador, entonces el reductor debe aplicar una modificación al acumulador en función del elemento actual y devolverlo:

(acc, el) => acc

O si el acumulador y los elementos tienen el tipo de sonido y son lógicamente iguales, no es necesario distinguirlos:

 (a, b) => a + b

¿Cuál es el valor inicial de la función de reducción?

Debería preguntarse "¿Qué debería reducir el rendimiento cuando se aplica en una matriz vacía?"

Ahora lo más importante: ¿Cuándo usar reducir? (OMI)

Si desea reducir los valores de una matriz en un solo valor u objeto .

Answer 4

Podría usar algunas funciones para obtener una matriz si no se proporciona una matriz, una función que devuelve una matriz ordenada tomando dos parámetros y una devolución de llamada de ordenación que incluye lo anterior al usar otro método de reducción para obtener un resultado parcial de una matriz ordenada.

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

Puedes usar una ordenación por inserción:

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)
  )
);

Esto creará la matriz de destino una vez y luego realizará inserciones en ella en cada paso de la reducción sin tener que recrear la matriz de destino.

Hay formas más eficientes de implementar countIfEqual pero elegí implementar todas las funciones utilizando reduce lugar de otras funciones de matriz.

Answer 6

Sin embargo, reducir no es ideal para la clasificación. La siguiente solución es como una función forEach o cualquier función de bucle que se intenta lograr con la función 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);

Tenga en cuenta que puede usar la función nativa Array.sort para ordenar y también puede tener su propia función de clasificación personalizada donde puede definir su propio algoritmo de clasificación.

Answer 7

Array.sort muta la matriz donde el uso de Array.reduce fomenta una función pura. Podrías clonar la matriz antes de ordenar.

Creo que esta pregunta está diseñada para que pienses de manera diferente al imponer restricciones. Pone a prueba su conocimiento de cómo funciona la reduce y, como muestran las respuestas, hay muchas formas de despellejar a un gato. Mostrará tu sabor personal de js para resolver esto.

Elegí usar Array.findIndex y 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, []);

Pruebas con la muestra de entrada produce

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

Answer 8

reduce restricciones a los algoritmos de ordenación en línea , donde cada elemento de la matriz se ve una vez y ahora no anticipa la longitud de su matriz (tenga en cuenta que al usar cierres se podría dar más información a la función de reducción, pero este tipo de derrotas cumplen el propósito de la pregunta).

La ordenación por inserción es un ejemplo obvio y fácil; No detallaré la implementación ya que las otras respuestas ya son muy buenas a este respecto. Sin embargo, puede mencionar algunas optimizaciones que probablemente sean muy positivas para el entrevistador:

• El uso de la búsqueda binaria para encontrar el punto de inserción puede reducir la complejidad de un paso de inserción de O (n) a O (log n). Esto se denomina ordenación por inserción binaria: el número total de comparaciones irá de O (n ^ 2) a O (n log n). Esto no será más rápido porque el costo real se debe a "empalmar" la matriz de salida, pero si tuviera comparaciones costosas (por ejemplo, la clasificación de cadenas largas, por ejemplo) podría hacer una diferencia.

• Si ordena enteros, puede usar la ordenación de radix e implementar un algoritmo de clasificación lineal en línea con reducir. Esto es bastante difícil de implementar, pero muy adecuado para una reducción.